Practice By Tag: A Recursively Defined Set
Question: 2015 Fall Final - 71 .
Consider strings of characters, each character being $a$, $b$, or $c$, that contain at least one $a$.
Let $S_n$ be the number of such strings having length $n$. Which of the following is true?
(a)
$S_n = 2 \cdot S_{n-1} + 3^{n-1}$
(b)
$S_n = 3 \cdot S_{n-1}$
(c)
None of the above.
(d)
$S_n = 2 \cdot S_{n-1} + 2 \cdot S_{n-2}$