Solution: 2014 Winter Midterm - 13

Author: Michiel Smid

Question

Let $B_n$ be the number of bitstrings of length $n$ that do not contain 111. Which of the following is true?

(a)

$B_n = B_{n-1} + B_{n-2} + B_{n-3}$

(b)

$B_n = B_{n-1} + B_{n-2} + 2^{n-3} - B_{n-3}$

(c)

$B_n = B_{n-1} + B_{n-2} + 2^{n-3}$

(d)

$B_n = B_{n-1} + B_{n-2} + B_{n-3} + 2^{n-4}$

We can write down some valid possibilities first.

$0, B_{n-1}$ possibilities left

$1,0, B_{n-2}$ possibilities left

$1,1,0, B_{n-3}$ possibilities left

Once we add up all possibilities, we get $B_n = B_{n-1}+B_{n-2}+B_{n-3}$