Finding the expression for $q_n$

Question

Let $q_n$ be the number of $n$-letter words consisting of letters a, b, c and d, and which contain an odd number of letters $b$. Prove that $$q_{n+1} = 2q_n + 4^n\qquad\forall n \geq 1 $$ and, starting from $q_1 = 1$, find the expression for the general term $q_n$.

Answer 1

Hints: For proving the recursive formula, note the following:

(1) $3q_n$ is the number of words of length $n+1$ formed from the letters $a,b,c,d$, containing an odd number of instances of $b$ and such that $b$ is not the first letter. (Why?)

(2) $4^n-q_n$ is the number of words of length $n$ formed from the letters $a,b,c,d$, containing an even number of instances of $b$. (Why?)

(3) $4^n-q_n$ is the number of words of length $n+1$ formed from the letters $a,b,c,d$, containing an odd number of instances of $b$ and such that $b$ is the first letter. (Why?)

For the last part, note that you should be able to get an explicit closed form entirely in powers of $2.$ (Why?) Check out the first several terms, and see if you can find a pattern to prove inductively.

Answer 2

Define $Q(z) = \sum_{n \ge 0} q_n z^n$, and $q_0 = 0$ is consistent with the recurrence. Then your recurrence gives: $$ \frac{Q(z) - q_0}{z} = 2 Q(z) + \frac{1}{1 - 4 z} $$ From here, as partial fractions: $$ Q(z) = \frac{1}{2} \cdot \frac{1}{1 - 4 z} - \frac{1}{2} \cdot \frac{1}{1 - 2 z} $$ Expanding the geometric series: $$ q_n = \frac{4^n - 2^n}{2} $$