Find a recurrence relation for the number of $n$-digit binary sequences with no pair of consecutive $1$s

Find a recurrence relation for the number of $n$-digit binary sequences with no pair of consecutive $1$s.

I know my base case:$$a_1 = 2$$ for either $1$ or $0$. Normally to construct the recurrent relation I would say fill in $n-1$ spaces then add a $1$ or $0$, which is simply:$$a_n = 2\cdot a_{n-1}$$However, I don't believe this is right, because this doesn't take into account that there can't be any consecutive $1$s.

Even when I use the base case of $2$ digits:$$a_2 = 3$$for either $01$, $10$, or $00$, I still get the recurrence relation of:$$a_n = 3\cdot a_{n-2}$$which also does not account for $01$ and $10$ occurring consecutively.

So how would I express this?

Solution 1:

The bit strings of length $1$, $\color{blue}{0}$ and $\color{blue}{1}$, do not have two consecutive ones, so $a_1 = 2$.

Of the four bit strings of length $2$, only $11$ has two consecutive ones. Hence, $a_2 = 4 - 1 = 3$. The permissible bit strings are $\color{green}{00}$, $\color{green}{01}$, and $\color{green}{10}$.

If $n = 3$, the permissible bit strings are $$\color{blue}{0}01, \color{blue}{1}01, \color{green}{00}0, \color{green}{01}0, \color{green}{10}0$$ where we have appended $01$ to the end of each permissible bit string of length $3 - 2 = 1$ and $0$ to the end of each permissible bit string of length $3 - 1 = 2$. Hence, $a_3 = a_2 + a_1 = 3 + 2 = 5$. As you can check, the other three bit strings of length $3$ have at least two consecutive ones.

Observe that if $n \geq 3$, then a bit string of length $n$ with no two consecutive $1$s that has a $1$ in the $n$th position must have a $0$ in the $(n - 1)$st position. Hence, to construct a bit string of length $n$ with no two consecutive $1$s that ends in $1$, we must append $01$ to the end of a bit string of length $n - 2$ that has no two consecutive $1$s. Any bit string of length $n$ with no two consecutive $1$s that has a $0$ in the $n$th position can be constructed by appending a $0$ to the end of a bit string of length $n - 1$ that has no two consecutive $1$s. Hence, for $n \geq 3$, $a_n = a_{n - 1} + a_{n - 2}$.

Thus, the number of permissible bit strings of length $n$ is given recursively by \begin{align*} a_1 & = 2\\ a_2 & = 3\\ a_n & = a_{n - 1} + a_{n - 2}, n \geq 3 \end{align*} Notice that $a_n = F_{n + 2}$, where $F_n$ denotes the $n$th Fibonacci number.

Solution 2:

You are thinking in the right direction. Suppose you want to construct a string of $n$ bits with no consecutive $1$s. Let this be done in $a_n$ ways.Then you can do the following:

i) Start with a zero, then construct a sequence of $n-1$ bits without any repeated ones. This can be done in $a_{n-1}$ ways.

ii) Start with a one, then because $1$s can't repeat, the next bit has to be a $0$, and now you construct a sequence having no repeated $1$s in $a_{n-2}$ ways.

So the recurrence relation should be $a_n=a_{n-1}+a_{n-2}$, with $a_0=0$ and $a_1=2$. From the above, $a_2=3$, which makes sense as you can see with $00,01,10$, $a_3=5$, as you can see with $000,001,010,100,101$.

So you got something Fibonacci"ish" in some sense.