Finding the expression for $q_n$ 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$.
 A: 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.
A: 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}
$$
