1 .
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} + 2^{n-4}$
(b)
$B_n = B_{n-1} + B_{n-2} + B_{n-3}$
(c)
$B_n = B_{n-1} + B_{n-2} + 2^{n-3}$
(d)
$B_n = B_{n-1} + B_{n-2} + 2^{n-3} - B_{n-3}$