Recurrence Relation

1. Dec 4, 2013

Miike012

I boxed the portion of the solution that I am questioning.

How come the number of invalid strings is only 3n-1 - an-1 and not
3(3n-1 - an-1) ?

As you can see there are three cases (Which are to the right of the black box)

In all the three cases, the portion boxed in red is a string of length n-1 and does not have any consecutive numbers

Case 1:
The first number is a 1, then the second number must also be a 1
so that the string has a pair of consecutive numbers

Case 2
The first number is a 2, then the second number must also be a 2
so that the string has a pair of consecutive numbers

Case 3
The first number is a 0, then the second number must also be a 0
so that the string has a pair of consecutive numbers

File size:
15.7 KB
Views:
96
2. Dec 5, 2013

HallsofIvy

Staff Emeritus
This is not true. There is no requirement that the "pair of consecutive numbers" be the first two. For example, 100 is a valid string with n= 3.

3. Dec 5, 2013

Miike012

The string of length n has the requirment that it must have a pair of consecutive numbers, so if the 2nd term through the nth term of the string don't have a pair of consecutive numbers then the first term and second term must be the same inorder to satisfy the requirement.

4. Dec 6, 2013

haruspex

I don't understand your logic. The reasoning in the attachment starts with an invalid string length n-1. By definition there are an-1 valid strings of that length, and obviously there are 3n-1 total strings of that length. Therefore there are (3n-1 - an-1) invalid strings length n-1. For each such invalid string, there is exactly one way of tacking on an nth (at the given end) to produce a valid string length n.
If that doesn't help, I'll need you to spell out your own reasoning more clearly.