Solution: 2014 Fall Final - 5
Author: Michiel SmidQuestion
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-3}\ \mathrm{for}\ n \geq 3.$
(b)
$S_n = 2 \cdot S_{n-1}\ \mathrm{for}\ n \geq 3.$
(c)
$S_n = S_{n-1} + S_{n-2} + S_{n-3}\ \mathrm{for}\ n \geq 3.$
(d)
$S_n = S_{n-1} + S_{n-2}\ \mathrm{for}\ n \geq 3.$
Solution
Let’s write out all recursive cases for $S_n$
- $0, S_{n-1} $
- $1, 0, S_{n-2} $