Find a recurrence relation for the number of strings of length $n$ that's composed of the letters $\{A,B,C,D\}$ such that each $A$ appears before $C$.
$a_n=\begin{cases} A\text{______} = a_{n-1} \\ B\text{______}= a_{n-1} \\ C\text{______}= 3^{n-1} \text{ all the strings without A}\\ D\text{______}= a_{n-1}\end {cases}$
So $a_n=3a_{n-1}+3^{n-1}$
Other than $C$ they all are trivial, but with $C$, can I force $A$ to be left out?
(Note: Here, I have assumed each $A$ appears directly before a $C$.)
Hint: We say a sequence is good if every $A$ is followed by a $C$. A good length-$n$ string has one of two possible forms:
it is a good length-$(n-1)$ string with one of $\{B,C,D\}$ appended, or
it is a good length-$(n-2)$ string with $AC$ appended.
This should give a clue as to what the recurrence relation relation should look like.
For the boundary case: we observe that $a_0=1$ and $a_1=3$.