Solution: 2017 Winter 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}$.
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}$

Solution

(The positions are numbered $ 1, 2, …, 3n-1) $.

Since the $ n^{th} $ position is 0, the $ {n-1}^{th} $ and $ {n+1}^{th} $ positions must be 1.

It would look something like: X,X,…,1,0,1,…,1,…,X,X

To the left of the first fixed 1, there are $ n - 2 $ bits that can be a, b, or c: $ f_{(n-2)+2} $ valid combinations
Between the second fixed 1 and third fixed 1, there are $ n - 2 $ bits that can be a, b, or c: $ f_{(n-2)+2} $ valid combinations
To the right of the third fixed 1, there are $ n - 1 $ bits that can be a, b, or c: $ f_{(n-1)+2} $ valid combinations

$ f_{n} \cdot f_{n} \cdot f_{n+1} $

$ {(f_{n})}^2 \cdot f_{n+1} $

Thus, the number of 00-free bitstrings of length $ 3n-1 $ that have 0 at position $ n $ and 1 at position $ 2n $ is $ {(f_{n})}^2 \cdot f_{n+1} $.