Find and solve a recurrence relation for the number of words of length n from letters A, B, C, and D

Question

Find and solve a recurrence relation for the number of words of length $n$ from letters $A, B, C,$ and $D$ which contain at least one $A$ and the first $A$ comes before the first $B$ (if there are any $B$s).

I can probably solve the recurrence relation, but I'm having a hard time coming up with relation to solve. I'm assuming that I need to look at where the first $A$ appears to get my equations.

Answer 1

Here are some thoughts.

A word of length $n$ that satisfies the criteria has $p$ $C$'s and $D$'s, where $0 \leq p < n$, followed by an $A$, followed by $q$ other letters (which can be any of $A,B,C,D$) where $q = n - p - 1$.

Given an example of a word of length $n$, you can construct a qualifying word of length $n+1$ by adding a $C$ or $D$ to the left side, or an $A,B,C,$ or $D$ to the right side.

Can you take it from here?

Answer 2

If you insist on using a recurrence relation, there are two types of legal strings of length $n$:

1. The last letter is not the first A. In this case, the first $n-1$ letters form a legal string of length $n-1$, for which there are $a_{n-1}$ choices, and there are 4 choices for the last character.
2. The last letter is the first A. In this case, the previous $n-1$ letters are an arbitrary string of Cs and Ds, of which there are $2^{n-1}$.

Adding this up, we get $a_n = 4a_{n-1} + 2^{n-1}$, with initial condition $a_1 = 1$ (only A is legal). Using the method of generating functions, this solves as $a_n=\frac12(4^n-2^n)$.