Question: 2017 Fall 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 20 that have 0 at position 7? (The positions are numbered $1,2,\dots,20$.)
What is the number of 00-free bitstrings of length 20 that have 0 at position 7? (The positions are numbered $1,2,\dots,20$.)
(a)
$f_{7} \cdot f_{14}$
(b)
$f_{7} \cdot f_{15}$
(c)
$f_{8} \cdot f_{15}$
(d)
$f_{8} \cdot f_{14}$