Solution: 2019 Winter Midterm - 10

Author: Michiel Smid

Question

A bitstring is called 00-free, if it does not contain two 0's next to each other. In class, we have seen that for any $m \geq 1$, the number of 00-free bitstrings of length $m$ is equal to the $(m+2)$-th Fibonacci number $f_{m+2}$.
What is the number of 00-free bitstrings of length 77 that have 0 at position 59? (The positions are numbered $1,2,\dots,77$.)

(a)

$f_{18} \cdot f_{58}$

(b)

$f_{20} \cdot f_{60}$

(c)

$f_{19} \cdot f_{59}$

(d)

$f_{17} \cdot f_{57}$

Solution

Because there is a 0 at position 59, there must be a 1 at position 58 and 60 to avoid a 00.

It looks something like this: …, 1, 0, 1, …, 1, …

The number of 00-free bitstrings made from the first 57 bits $ \text{bit positions 1 to 57} $ is $ f_{57+2} $.

The number of 00-free bitstrings made from the 17 bits $ \text{bit positions 61 to 77} $ is $ f_{17+2} $.

Thus, the number of 00-free bitstrings with the above conditions is $ f_{59} \cdot f_{19} $.