Question: 2015 Fall Midterm - 11
Let $S_n$ be the number of bitstrings of length $n$ that contain the substring 0000. Which of the
following is true?
(a)
$S_n = S_{n-1} + S_{n-2} + S_{n-3} + S_{n-4}$
(b)
$S_n = S_{n-1} + S_{n-2} + S_{n-3} + S_{n-4}\ +$ $ 2^{n-4}$
(c)
$S_n = S_{n-1} + S_{n-2} + S_{n-3}$
(d)
$S_n = S_{n-1} + S_{n-2} + S_{n-3} + 2^{n-3}$