Question: 2019 Winter Midterm - 12
Consider strings of characters, where each character is an element of the set $\{a, b, c\}$. Such a
string is called awesome, if it does not contain $aa$, and does not contain $aba$, and does not contain $abb$.
For any integer $n \geq 1$, let $A_n$ be the number of awesome strings of length $n$.
Which of the following is true for any integer $n \geq 4$?
For any integer $n \geq 1$, let $A_n$ be the number of awesome strings of length $n$.
Which of the following is true for any integer $n \geq 4$?
(a)
$A_n = A_{n-1} + 2 \cdot A_{n-2} + 2 \cdot A_{n-3}$
(b)
$A_n = 2 \cdot A_{n-1} + A_{n-2} + A_{n-3}$
(c)
$A_n = 2 \cdot A_{n-1} + A_{n-2} + 2 \cdot A_{n-3}$
(d)
$A_n = A_{n-1} + 2 \cdot A_{n-2} + A_{n-3}$