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

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

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