Let $a_n$ be the number of words of length n over the alphabet {A, B, C} such that any nonterminal A has to be immediately followed by B. Find $a_n$.
Here's what I know: If the word starts with $C$ or $B$, any valid sequence of length $n-1$ will work to complete the word.
If the word starts with $A$, it must be followed with $B$, then any valid sequence of length $n-2$, so I get a recurrence relation of: $$a_n = 2a_{n-1} + a_{n-2}.$$
How could I solve for $a_n$?
On
Denote by $W_n$ the number of words in $n$ characters satisfying your condition, by $A_n$ the number of those words ending in $A$, similarly $B_n$ and $C_n$.
Then we have $W_n=A_n+B_n+C_n$. Moreover, $B_n=W_{n-1}$, while $A_n=C_n=B_{n-1}+C_{n-1}=W_{n-1}-A_{n-1}$. Therefore, $W_n=3W_{n-1}-2A_{n-1}$.
Thus, $(W_n,A_n)=(3W_{n-1}-2A_{n-1},W_{n-1}-A_{n-1})$, while $A_1=1$ and $W_1=3$. This is a standard linear recurrence, so I leave it to you to find the closed formula.
This can be done recursively. We have $a_1 = 3$ and $a_2 = 7$ by inspection.
Then for $n>2$, we see that there are three possible ways to start a sequence: $AB$, $B$, or $C$. Depending on which one we choose, we recurse into a smaller sequence of known size, where the counting process is repeated all over again.
This suggests the recurrence $a_n = 2a_{n-1} + a_{n-2}$ with $a_1 = 3$ and $a_2 = 7$.
To get a closed form, note that the characteristic polynomial is $x^2 - 2x - 1 = 0$, or $(x-1)^2-2 = 0$, which has roots $1 + \sqrt{2}$ and $1 - \sqrt{2}$. Therefore:
$a_n = A(1 + \sqrt{2})^n+B(1 - \sqrt{2})^n$ for some unknown $A,B$.
But we already know $a_1$ and $a_2$:
$3 = A(1 + \sqrt{2})^1+B(1 - \sqrt{2})^1$
$7 = A(1 + \sqrt{2})^2+B(1 - \sqrt{2})^2$
Solving this system yields $A = \frac{1}{2}+\frac{1}{\sqrt{2}}, B = \frac{1}{2}-\frac{1}{\sqrt{2}}$. Therefore:
$$a_n = (\frac{1}{2}+\frac{1}{\sqrt{2}})(1 + \sqrt{2})^n+(\frac{1}{2}-\frac{1}{\sqrt{2}})(1 - \sqrt{2})^n$$
Simplifying:
$$a_n = \frac{1}{2} ((1+\sqrt{2})^{n+1}+(1-\sqrt{2})^{n+1})$$