Question: 2018 Winter Midterm - 11
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 55 that have 0 at position 9, and 1 at position 40? (The positions are numbered $1,2,\dots,55$.)
What is the number of 00-free bitstrings of length 55 that have 0 at position 9, and 1 at position 40? (The positions are numbered $1,2,\dots,55$.)
(a)
$f_8 \cdot f_{30} \cdot f_{16}$
(b)
$f_9 \cdot f_{31} \cdot f_{17}$
(c)
$f_{10} \cdot f_{32} \cdot f_{18}$
(d)
$f_7 \cdot f_{29} \cdot f_{15}$