Question: 2014 Winter Final - 5
Consider strings consisting of $n$ characters, each character being $a$, $b$, or $c$. Let $S_n$ be the
number of such strings of length $n$ that do not contain the substring $aa$. Which of the following
is true?
(a)
$S_{n+1} = 2 \cdot S_n + S_{n-1}\ \mathrm{for}\ n \geq 2.$
(b)
$S_{n+1} = S_n + 2 \cdot S_{n-1}\ \mathrm{for}\ n \geq 2.$
(c)
$S_{n+1} = 2 \cdot S_n + 2 \cdot S_{n-1}\ \mathrm{for}\ n \geq 2.$
(d)
$S_{n+1} = S_n + S_{n-1}\ \mathrm{for}\ n \geq 2.$