Bit strings with at most two consecutive identical digits

Question

I am trying to develop a recurrence relation for $T(n)$, the number of bit strings of length $n$ with a maximum of two consecutive $0$s or $1$s

I find the recurrence relation $$T(n) = 2T(n-1) + T(n-2)$$ Is this right?

Answer 1

Consider the following graph:

For each binary string we start from the blue state (empty string) and move along the graph according to the next character (I didn't mark them to the arrows but it should be obvious which is which, anyway it doesn't matter for the calculation).

Consider the walks of length $n$ along the graph (or in another words binary strings of length $n$). For each state $X$ we want to count the number of these that start from the blue state and end up in $X$. By symmetry, this number is same for states $0$ and $1$, denote this by $a_n$. Similarly for the states $00$ and $11$, denote this by $b_n$. For the blue state, this number is $1$ for $n=0$ and $0$ otherwise.

Now we can see from the graph that

• $a_n = a_{n-1}+b_{n-1}$ and $a_0=0, \space a_1=1$
• $b_n = a_{n-1}$ and $b_0=0, \space b_1=0, b_2=1$

From these we get $a_{n}=a_{n-1}+a_{n-2}$ which is the familiar Fibonacci numbers. So $a_n=f_n$.

We want to count the strings that aren't rejected: $T_n = 2(a_n+b_n) = 2(f_n+f_{n-1})=2f_{n+1}$, (and the blue state), so we have

$$T_n = 2f_{n+1}, \space n>0, \text{ and } T_0=1$$