Question: 2017 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}$.
Let $n \geq 3$ be an integer. What is the number of 00-free bitstrings of length $3n-1$ that have 0 at position $n$ and 1 at position $2n$? (The positions are numbered $1,2,\dots,3n-1)$.
(n.b., $f^2_x = f_x \cdot f_x$)
Let $n \geq 3$ be an integer. What is the number of 00-free bitstrings of length $3n-1$ that have 0 at position $n$ and 1 at position $2n$? (The positions are numbered $1,2,\dots,3n-1)$.
(n.b., $f^2_x = f_x \cdot f_x$)
(a)
${f^2_{n+1}} \cdot f_n$
(b)
${f^2_{n}} \cdot f_{n+1}$
(c)
${f^2_{n+1}} \cdot f_{n+2}$
(d)
${f^2_{n+2}} \cdot f_{n+1}$