Solution: 2015 Fall Final - 7

Author: Michiel Smid

Question

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)

$S_n = 2 \cdot S_{n-1} + 2 \cdot S_{n-2}$

(d)

None of the above.

Solution

Let’s write out the possibilities I guess

$ b, S_{n-1} $
$ c, S_{n-1} $
$ a, 3^{n-1} $ because we could have our first $a$ here, and the rest of the string can be any of the 3 characters

$ S_n = 2 \cdot S_{n-1} + 3^{n-1} $