1 .
Let $B_n$ be the number of bitstrings of length $n$ that do not contain 1111. Which of the following
is true?
(a)
$B_n = B_{n-1} + B_{n-2} + B_{n-3}$
(b)
$B_n = 2^{n} - (n-3) \cdot 2^{n-4}$
(c)
$B_n = B_{n-1} + B_{n-2} + B_{n-3} + B_{n-4}$
(d)
$B_n = 2^{n} - 2^{n-4}$