0

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.

Mark Fantini
  • 5,523
user132226
  • 161
  • 2
    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. – Andrés E. Caicedo Mar 01 '14 at 01:56

1 Answers1

0

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.

qwr
  • 10,716
  • 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$. – Andrés E. Caicedo Mar 01 '14 at 02:16
  • @AndresCaicedo I was considering that, but I wasn't sure. I'm going to change it. – qwr Mar 01 '14 at 02:25
  • 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. – Andrés E. Caicedo Mar 01 '14 at 02:36