Question: 2017 Winter Midterm - 13
For any integer $n \geq 1$, let $B_n$ be the number of bitstrings of length $n$ that do not contain
the substring 10. Which of the following is true for any $n \geq 4$?
(a)
$B_n = n+1$
(b)
$B_n = n$
(c)
$B_n = f_{n+2}$, the $(n+2)$-nd Fibonacci number.
(d)
$B_n = f_{n+1}$, the $(n+1)$-st Fibonacci number.