## Zeros and ones

Prove that the number of sequences of zeros and ones of length $$n$$ that do not contain two zeroes in a row equals $$F_{n+2}$$.

• #### Solution

Let $$p_n$$ be the number of sequences of length $$n$$ that do not contain two zeros next to each other.

For the first two values of $$n$$, $$p_1 = | \{1{,}0 \} | = 2 = F_3$$ and $$p_2 = | \{11{,}10,01 \} | = 3 = F_4$$.

For $$n \ge 3$$ we proceed by induction.

We consider the considered sequences of length $$n$$ into two groups: Those that end in one and those that end in zero.

The size of the first group is $$p_{n-1}$$, because any sequence of length $$n$$ ending in one can be obtained from a sequence of length $$n-1$$ not containing two zeros side by side by crediting one to the end.

In the second group, we first notice that it necessarily ends with a pair of 10. Previous $$n-2$$ symbols is any sequence without two zeros next to each other. Of these sequences, including the size of the second group, is $$p_{n-2}$$.

We got a recurrent relation $$p_n = p_{n-1} + p_{n-2}$$. According to the inductive assumption, we can assume that the proved relation holds for all numbers less than $$n$$, among others also for $$p_{n-1} = F_{n-3}$$ and $$p_{n-2} = F_{n-4}$$. Substituting the corresponding Fibonacci number on the right, we get $$p_n = p_{n-1} + p_{n-2} = F_{n-3} + F_{n-4} = F_{n-2}$$.