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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.