Solution: 2017 Fall Midterm - 11

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 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}$

Solution

If there is a 0 at position 7, position 6 and 8 must be 1.

It would look something like: XXXXX101XXXXXXXXXXXX

Because the first 5 bits are 00-free bitstrings of length 5, there are $ f_{5+2} $ combinations.

Bitstrings from position 9 to 20 are 00-free bitstrings of length 12, there are $ f_{12+2} $ combinations.

Thus, there are $ f_{7} \cdot f_{14} $ combinations.