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.

  • 2
    $\begingroup$ Consider two cases: Whether the first letter in the word is one, or whether it is zero. Count the number of words in each case, in terms of the previous $U_i$s. $\endgroup$ – Andrés E. Caicedo Mar 1 '14 at 1:56


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.

  • $\begingroup$ I think you want a different name for $\{0,1\}$ (the set, note that $U_1$ is the size of the set, rather than the set itself). Same for $U_2,U_3$. $\endgroup$ – Andrés E. Caicedo Mar 1 '14 at 2:16
  • $\begingroup$ @AndresCaicedo I was considering that, but I wasn't sure. I'm going to change it. $\endgroup$ – qwr Mar 1 '14 at 2:25
  • $\begingroup$ Some suggestions: $U_n$ counts $A_n$ (rather than describe it). Then, you look at the first number of a word in $A_3$, and can put any word in $A_2$ at the end. Similar changes at other places of course. $\endgroup$ – Andrés E. Caicedo Mar 1 '14 at 2:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.