1 .
Consider bitstrings that do not contain 110. Let $S_n$ be the number of such strings having
length $n$.
Which of the following is true for any $n \geq 4$?
(a)
$S_n = S_{n - 1} + S_{n - 2} + S_{n - 3}$
(b)
$S_n = S_{n - 1} + S_{n - 2} + 2^{n - 3}$
(c)
$S_n = S_{n - 1} + S_{n - 2} + 1$
(d)
$S_n = S_{n - 1} + S_{n - 2} + 2^{n - 2}$