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.
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$.