How many sequences with different neighbours? I need to compute how many n-element binary-sequences exists, that two neighbour elements are not 1. For instance n=5 we have:
00000
00001
00010
00100
01000
10000
10001
10010
10100
01001
01010
00101
10101
There are 13 such binary-sequences.
 A: Observe that $a_1 = 2$ since both $0$ and $1$ are permissible sequences and that $a_2 = 3$ since $00$, $01$, and $10$ are permissible sequences.  Suppose $k \geq 3$.  We can extend a permissible sequence of length $k - 1$ to a sequence of length $k$ by appending a $0$ to the end of the sequence.  However, since no two $1$'s can be consecutive, we can only obtain a sequence of length $k$ that ends in a $1$ if we append $01$ to a sequence of length $k - 2$.  Hence, we have the recurrence relation
\begin{align*}
a_1 & = 2\\
a_2 & = 3\\
a_k & = a_{k - 1} + a_{k - 2}, k \geq 3
\end{align*}
As you can check, $a_k = F_{k + 2}$, where $F_k$ is the $k$th number of the Fibonacci sequence.
A: Let $a_n$ denote the number of these sequences that start with $1$ and let $b_n$ denote the number of these sequences that start with $0$.
Then:


*

*$a_{n+1}=b_n$

*$b_{n+1}=a_n+b_n$


Looking at scheme:
$\begin{array}{ccccccc}
n &  & 1 & 2 & 3 & 4 & 5\\
a_{n} &  & 1 & 1 & 2 & 3 & 5\\
b_{n} &  & 1 & 2 & 3 & 5 & 8\\
a_{n}+b_{n} &  & 2 & 3 & 5 & 8 & 13
\end{array}$
we immediately "smell" Fibonacci, and the appearing conjecture can easily be proved with induction.
