Question: 2018 Fall Midterm - 13

Author: Michiel Smid

Consider strings of characters, where each character is one of the 26 lowercase letters $a,b,c,\dots,z$. Such a string is called $qq$-free, if it does not contain two $q$'s next to each other. For any integer $n \geq 1$, let $Q_n$ be the number of $qq$-free strings of length $n$.
Which of the following is true for any integer $n \geq 3$?

(a)

$Q(n) = 26 \cdot Q(n-1) + 26 \cdot Q(n-2)$

(b)

$Q(n) = 25 \cdot Q(n-1) + 26 \cdot Q(n-2)$

(c)

$Q(n) = 26 \cdot Q(n-1) + 25 \cdot Q(n-2)$

(d)

$Q(n) = 25 \cdot Q(n-1) + 25 \cdot Q(n-2)$