Zeros and ones

Task number: 3317

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} \).

Difficulty level: Easy task (using definitions and simple reasoning)
Routine calculation training
Cs translation
Send comment on task by email