Solution: 2014 Winter Final - 5

Author: Michiel Smid

Question

Consider strings consisting of $n$ characters, each character being $a$, $b$, or $c$. Let $S_n$ be the number of such strings of length $n$ that do not contain the substring $aa$. Which of the following is true?

(a)

$S_{n+1} = 2 \cdot S_n + 2 \cdot S_{n-1}\ \mathrm{for}\ n \geq 2.$

(b)

$S_{n+1} = 2 \cdot S_n + S_{n-1}\ \mathrm{for}\ n \geq 2.$

(c)

$S_{n+1} = S_n + S_{n-1}\ \mathrm{for}\ n \geq 2.$

(d)

$S_{n+1} = S_n + 2 \cdot S_{n-1}\ \mathrm{for}\ n \geq 2.$

Solution

Let’s consider all possible recursive cases for the strings of length $n$.

$b, S_{n-1}$

$c, S_{n-1}$

$a, b, S_{n-2}$

$a, c, S_{n-2}$

Adding it up, we get $S_n = S_{n-1} + S_{n-1} + S_{n-2} + S_{n-2} = 2S_{n-1} + 2S_{n-2}$

Because the question asks for the case of $n+1$, we can substitute $n+1$ into the equation

$S_{n+1} = 2S_{n} + 2S_{n-1}$