Question: 2015 Winter Midterm - 11
Consider strings consisting of the characters $a$, $b$, and $c$. Such a string is called valid,
if it does not contain the substring $aaa$. Let $S_n$ be the number of valid strings of length
$n$. Which of the following is true?
(a)
$S_n = 2 \cdot S_{n-1} + 2 \cdot S_{n-2} + S_{n-3}$
(b)
$S_n = 2 \cdot S_{n-1} + 2 \cdot S_{n-2} + 2 \cdot S_{n-3}$
(c)
$S_n = 2 \cdot S_{n-1} + 2 \cdot S_{n-2}$
(d)
$S_n = 2 \cdot S_{n-1} + S_{n-2} + 2 \cdot S_{n-3}$