Question: 2019 Winter Final - 9
Consider bitstrings that do not contain 011 and have 1 at every even position.
(The positions are numbered $1,2,3,...$). Let $S_n$ be the number of such strings having
length $n$. Which of the following is true for any $n \geq 3$?
(a)
$S_n = S_{n - 1} + S_{n - 3}$
(b)
$S_n = S_{n - 2} + S_{n - 3}$
(c)
$S_n = 1 + S_{n - 1}$
(d)
$S_n = 1 + S_{n - 2}$