Question: 2014 Fall Final - 5
Let $S_n$ be the number of bitstrings of length $n$ that do not contain the substring 11. Which of
the following is true?
(a)
$S_n = S_{n-1} + S_{n-2} + S_{n-3}\ \mathrm{for}\ n \geq 3.$
(b)
$S_n = S_{n-1} + S_{n-3}\ \mathrm{for}\ n \geq 3.$
(c)
$S_n = S_{n-1} + S_{n-2}\ \mathrm{for}\ n \geq 3.$
(d)
$S_n = 2 \cdot S_{n-1}\ \mathrm{for}\ n \geq 3.$