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?
Best Answer
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.