Solution: 2017 Winter Midterm - 13

Author: Michiel Smid

Question

For any integer $n \geq 1$, let $B_n$ be the number of bitstrings of length $n$ that do not contain the substring 10. Which of the following is true for any $n \geq 4$?

(a)

$B_n = f_{n+2}$, the $(n+2)$-nd Fibonacci number.

(b)

$B_n = n+1$

(c)

$B_n = n$

(d)

$B_n = f_{n+1}$, the $(n+1)$-st Fibonacci number.

Solution

If we start with a 1, then all other bits need to be 1 to not contain the substring 10.

The other possibilties are a set of 0’s followed by a set of 1’s.

If n=4, then the possibilities are:

0000

0001

0011

0111

These are 4 possibilities.

Thus, there are $ n+1 $ possibilities.