Question: 2015 Winter Final - 7
Consider strings of characters, each character being $a$, $b$, or $c$, that contain an odd number of
$a$s. Let $S_n$ be the number of such strings having length $n$. Which of the following is true?
(a)
$S_n = S_{n-1} + S_{n-2}$
(b)
$S_n = 2 \cdot S_{n-1} + S_{n-2}$
(c)
$S_n = 2 \cdot S_{n-1} + (3^{n-1} - S_{n-1})$
(d)
$S_n = S_{n-1} + (3^{n-1} - S_{n-1})$