Solution: 2015 Winter Midterm - 11

Author: Michiel Smid

Question

Consider strings consisting of the characters $a$, $b$, and $c$. Such a string is called valid, if it does not contain the substring $aaa$. Let $S_n$ be the number of valid strings of length $n$. Which of the following is true?

(a)

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

(b)

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

(c)

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

(d)

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

Solution

We can write down some valid possibilities first.

$b, B_{n-1}$ possibilities left
$c, B_{n-1}$ possibilities left
$a,b, B_{n-2}$ possibilities left
$a,c, B_{n-2}$ possibilities left
$a,a,b, B_{n-3}$ possibilities left
$a,a,c, B_{n-3}$ possibilities left

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