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?
 A: 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.
A: 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.
