1 .
Consider strings of characters, each character being $a$ or $b$, that contain at least one
occurrence of $aa$. Let $S_n$ be the number of such strings having length $n$. Which of the
following is true for $n \geq 4$?
(a)
$S_n = S_{n-1} + S_{n-2} + S_{n-3}$
(b)
$S_n = S_{n-1} + 2 \cdot S_{n-2}$
(c)
$S_n = S_{n-1} + S_{n-2} + 2^{n-2}$
(d)
$S_n = S_{n-1} + S_{n-2} + 2^{n-3}$