Solution: 2018 Fall Midterm - 13

Author: Michiel Smid

Question

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) = 25 \cdot Q(n-1) + 26 \cdot Q(n-2)$

(b)

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

(c)

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

(d)

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

Solution

Let’s write down some possibilities

$ \text{any of the 26 letters excluding q=25 possible letters}, Q_{n-1} $

$ q, \text{any of the 26 letters excluding q=25 possible letters}, Q_{n-2} $

$ Q_n = 25 \cdot Q_{n-1} + 25 \cdot Q_{n-2} $