Let Un be the number of words with length $n$ in the alphabet ${0,1}$ that have the property of not having consecutive zeros. Prove that:
$$U_1 = 2, U_2= 3, U_n = U_{n-1} + U_{n-2}.$$
I am stuck with this proof ... I know that this is related somehow to the fibonacci sequence and that the theorem might be proved by using strong mathematical induction. Any help is appreciated.
Hint:
Let $A_n$ be the words $U_n$ describes.
$A_1 = \{0,1\}$
$A_2 = \{01,10,11\}$
How can you write $A_3$ in terms of $A_1$ and $A_2$? Let's have the first number of $A_3$ be either $0$ or $1$ and put $A_2$ at the end. If you start with a $1$, any $A_2$ will make $A_3$ valid. If you start with a $0$ and $A_2$ starts with a $1$, $A_3$ will be valid. So there are $2+3$ cases, which also is $U_2 + U_1$.
$A_3 = \{010, 011, 101, 110, 111\}$
Now try it with $A_4$. There are $3$ cases that start with $1$. This is $U_2$. Can you see why? Then, if the starting number of $A_4$ is $1$, then everything in $U_3$ works. The number of elements in $U_4 = U_3 + U_2$.
Hopefully you can take it from there.