Question: 2014 Winter Midterm - 13

Author: Michiel Smid

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