Question: 2016 Fall Midterm - 11
For any integer $n \geq 1$, let $B_n$ be the number of bitstrings of length $n$ that do not
contain the substring 11 and do not contain the substring 101. Which of the following is true
for any $n \geq 4$?
(a)
$B_n = B_{n - 2} + B_{n - 4}$
(b)
$B_n = B_{n - 2} + B_{n - 3}$
(c)
$B_n = B_{n - 1} + B_{n - 3}$
(d)
$B_n = B_{n - 1} + B_{n - 2}$