Counting with recurrence: Strings which avoid the substring $AB$. Let $X(n)$ be the number of length $n$ strings from the alphabet $\{A,B,C,D\}$ which avoid the substring $AB$. Write a recurrence for $X(n)$ and explain in words why it satisfies the recurrence.

My attempt:

Any length $n$ string sequence must start with either $A,B,C,D$. If it starts with $B,C,D$, we don't need to worry about the what follows right after, so the number of length $n$ strings that avoid $AB$ and start with $B,C,D$ is $3X(n-1)$. Now we deal with the case when it starts with $A$. If it starts with $A$, the next letter must be either $A,C,D$, only three choices, which means the rest of the sequence can be any $n-2$ length string which avoids $AB$. The number of length $n$ strings which start with $A$ and which avoid $AB$ is $3X(n-2)$, so we get
\begin{cases} 
X(0)=1\\[4pt]
X(1)=4\\[4pt]
X(n)=3X(n-1)+3X(n-2),\;\text{if}\;n\ge 2\\
\end{cases}
However the solution is:
\begin{cases} 
X(0)=1\\[4pt]
X(1)=4\\[4pt]
X(n)=4X(n-1)-X(n-2),\;\text{if}\;n\ge 2\\
\end{cases} 
Note that for $n=2$, the results are the same, but they are not the same for $n=3$. 

Please let me know what I missed in my attempt. Thank you.
 A: As to where you went wrong, your statement

$\;\;\;\;$The number of length $n$ strings which start with $A$ and which avoid $AB$ is $3X(n-2)$

is not correct, since for $n \ge 3$, it includes some strings which start with $AAB$.

A correct recursion can be achieved as follows . . .

By direct count, we get $x(0) = 1$ (the empty string), and $x(1) = 4$ (any string of length $1$).

Suppose $n \ge 2$. 

Consider the count of all $n$-term sequences $s$ for which the $(n-1)$-term subsequence $s'$ with the first term of $s$ removed is such that $s'$ avoids the subsequence $AB$.

Since we are allowing all possible first terms for $s$, the count is $4x(n-1)$.

But this is an overcount since it allows sequences $s$ which start with $AB$.

To correct the count, subtract the count of those already counted sequences which start with $AB$. 

Thus, we need to subtract the count of the sequences $s=ABs''$ such that the $(n-2)$-term sequence $s''$ avoids the subsequence $AB$, and there are $x(n-2)$ of those.

Hence, for $n \ge 2$, we get $x(n) = 4x(n-1) - x(n-2)$.

As an alternate approach, you can use a linked recursion. 

It's a little more work, but I think the logic is simpler.

Here's how it would go . . .

Let $x(n)$ be the number of qualifying $n$-term sequences with no immediately preceding $A$, and let $y(n)$ be the number of qualifying $n$-term sequences with an immediately preceding $A$. 

Then for $n > 0$, we get
\begin{align*}
x(n) &= 3x(n-1) + y(n-1)\\[4pt]
y(n) &= y(n-1)+ 2x(n-1)
\end{align*}
and for $n=0$, we have $x(0) = 1,\;y(0) = 1$.

To unlink the recursion, solve the equation
$$x(n) = 3x(n-1) + y(n-1)$$
for $y(n-1)$, which yields
$$y(n-1) = x(n) - 3x(n-1)$$
which implies
$$y(n) = x(n+1) - 3x(n)$$
Then, replacing $y(n)$ and $y(n-1)$ in the equation
$$y(n) = y(n-1)+ 2x(n-1)$$
yields
$$x(n+1) = 4x(n) - x(n-1)$$
or equivalently,
$$x(n) = 4x(n-1) - x(n-2)$$
valid for all $n > 1$, with initial values $x(0) = 1,\;x(1) = 4$.
A: In his answer quasi has pointed out your error. As for the correct recurrence, you can argue as follows:
An admissible word of length $n$ begins with one of $A$, $B$, $C$, $D$ and is followed by an admissible word of length $n-1$. We therefore would have $X(n)=4 X(n-1)$. Now this does include words which begin with $AB$, but are otherwise admissible. There are $X(n-2)$ of these. Discounting them we obtain the recursion
$$X(n)=4X(n-1)-X(n-2)\ .$$
