Prove that $a_{n} = a_{n-1} + a_{n-2}$

Question

For all $n\geq 1$ we have a set $\begin{Bmatrix} 0,1 \end{Bmatrix}^n$ that only consists of $0$'s and $1$'s. Let $G_{n}$ be the set containing all elements except elements where two $1$'s are standing next to each other.

So e.g. $G_{3} = \begin{Bmatrix} (0,0,0),(1,0,0),(0,1,0),(0,0,1),(1,0,1) \end{Bmatrix}$
Now let $a_{n}$ be the amount of elements in $G_{n}$. So $a_{3} = 5$.

I have to prove that $a_{n} = a_{n-1} + a_{n-2}$ for all $n\geq 3$. I know that each set contains $n-1$ elements ending with $1$ as its given that two $1$'s can't stand next to each other. Now let $x$ be the elements ending with a $0$. We can define that $a_{n} = n-1+x$. But if I fill this in $a_{n-1}$ and $a_{n-2}$ it seems that I can't get anything out of it.

Answer 1

Suppose $b_n$ counts the number of length $n$ acceptable sequences which end with $(\ldots,0)$ and $c_n$ counts the number of length $n$ acceptable sequences which end with $(\ldots,0,1)$. Then it should be easy to see

• $a_n=b_n+c_n$ since endings with $(\ldots,1,1)$ are not acceptable
• $b_n=a_{n-1}$ since you just stick $0$ on the end of a shorter acceptable sequence
• $c_n=a_{n-2}$ since you just stick $0,1$ on the end of a shorter acceptable sequence