The number of strings of length $n$ consisting of symbols $A,B,C$ not containing substring $CC$

Question

So I'm wondering what is wrong with my reasoning.

Let $a_n$ be the number of strings of length $n$ in letters $A,B,C$ not containing substring $CC$.

I want to solve it like this. Let $b_n$ be the number of strings which end with $A$ or $B$ and $c_n$ be the number of strings that end with $C$.

For a string of length $n-1$ that ends with $A$ or $B$ there is three choices to append a symbol. For a string of same length but ends with $C$ there are two choices so we have $a_n=3b_{n-1}+2c_{n-1}$. Since $b_{n-1}+c_{n-1}=a_{n-1}$ and $b_{n-1}=a_{n-2}$ we have $a_n=3b_{n-1}+2c_{n-1}=a_{n-2}+2a_{n-1}$

I'm not sure but I think the correct solution is $a_n=2a_{n-2}+2a_{n-1}$. The answer is of no matter though, I would like to know what is wrong my reasoning.

Explanation of my reasoning. So first I try calculate $a_n$ from $b_{n-1}$ and $c_{n-1}$. I consider the strings of length $n-1$, they either end with $A$, $B$ or $C$. If they end with $A$ or $B$ then I have $3$ choices to append a symbol to the string so it becomes string of length $n$ thus there $3b_{n-1}$ strings where the second to last symbol is $A$ or $B$.

Further, consider the string of length $n-1$ where the last symbol is $C$. Then there are two choices append a symbol so there are $2c_{n-1}$ strings where the second to last symbol is C.

Then I add up the strings which the second to last symbol is $A$ or $B$ and $C$ and get $a_n=3b_{n-1}+2c_{n-1}$.

Answer 1

Here is a systematic approach with a convenient notation which helps to derive recurrence relations of this kind.

We count the number $a_n$ of valid strings of length $n$ from the set $\{A,B,C\}$, i.e. strings which do not contain $CC$. We do so by partitioning them according to their matching length with the initial parts of the bad string $CC$. We consider \begin{align*} \color{blue}{a_n=a^{[\emptyset]}_n+a^{[C]}_n}\tag{1} \end{align*}

• The number $a^{[\emptyset]}_n$ counts the valid strings of length $n$ which do not start with the rightmost character of the bad word $CC$, i.e. start with $A$ or $B$.

• The number $a^{[C]}_n$ counts the valid strings of length $n$ which do start with the rightmost character of the bad word $CC$, i.e. $C$.

We get a relationship between valid strings of length $n$ with those of length $n+1$ as follows:

• If a word counted by $a^{[\emptyset]}_n$ is appended by $A$ or $B$ from the left it contributes to $a^{[\emptyset]}_{n+1}$. If it is appended by $C$ from the left it contributes to $a^{[C]}_{n+1}$.

• If a word counted by $a^{[C]}_n$ is appended by $A$ or $B$ from the left it contributes to $a^{[\emptyset]}_{n+1}$. Appending from the left by $C$ is not allowed since then we have an invalid string starting with $CC$.

This relationship can be written as

\begin{align*} \color{blue}{a^{[\emptyset]}_{n+1}}&\color{blue}{=2a^{[\emptyset]}_{n}+2a^{[C]}_{n}}\tag{2}\\ \color{blue}{a^{[C]}_{n+1}}&\color{blue}{=a^{[\emptyset]}_n}\tag{3} \end{align*}

We can now derive a recurrence relation from (1) - (3):

We obtain for $n\geq 1$: \begin{align*} \color{blue}{a_{n+1}}&=a^{[\emptyset]}_{n+1}+a^{[C]}_{n+1}\tag{$ \to (1)$}\\ &=\left(2a^{[\emptyset]}_{n}+2a^{[C]}_{n}\right)+\left(a^{[\emptyset]}_{n}\right) \tag{$\to (2),(3)$}\\ &=2a_{n}+\left(2a^{[\emptyset]}_{n-1}+2a^{[C]}_{n-1}\right)\tag{$\to (1),(2)$}\\ &\,\,\color{blue}{=2a_n+2a_{n-1}}\tag{$\to (1)$} \end{align*} as given in the other answer.

Answer 2

Simple reasoning gives us $b_n = 2 (b_{n-1} + c_{n-1})$ and $c_n = b_{n-1}$.

We therefore have

$\begin{align} a_n &= b_n + c_n \\ &= 2( b_{n-1} + c_{n-1} ) + b_{n-1} \\ &= 2( b_{n-1} + c_{n-1} ) + 2( b_{n-2} + c_{n-2} ) \\ &= 2a_{n-1} + 2a_{n-2}. \end{align}$