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$?
Best Answer
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})$$