Let $a_n$ be the number of $X$-strings of length $n$ that do not contain $344$ as a sub-string. Find a recurrence relation for $a_n$.

Question

Let $X = \{1,2,3,4\}$ and $a_n$ be the number of $X$-strings of length $n$ that do not contain $344$ as a sub-string.

Find a recurrence relation for $a_n$.

---

We can construct a string of length $n$ in the following ways:

$1.$ String of length $n-1$ and $1/2/3$ in the last place.

$2.$ String of length $n-2$ and $14/24/34$ in the last two places.

$3.$ String of length $n-3$ and $144/244/444$ in the last three places.

Hence the required recurrence relation for $a_n$ is $$a_n = 3a_{n-1}+3a_{n-2}+3a_{n-3}$$ with initial conditions $a_0 = 1,a_1 = 4$ and $a_2 = 16$.

---

Is the argument valid?

Answer 1

As i said in the comment your answer goes wrong when $n\geq 4$ , so let me give you a tricky way to solve it.

As you said all strings can end up with any of these $4$ letters and assume that these strings do not contain $344$ in it , so there are $4a_{n-1}$ such strings.

Now , think the string which ends up with $4$ and do not contain $344$.It has $a_{n−1}$ string that do not have $344$ , but this $a_{n−1}$ string might end with $34$. Because of this, we must subtract the sequence which end up with $4$ and have a substring with length $n−1$ but ends with $34$.

$$a_n=4a_{n-1}-a_{n-3}, \text{where $a_0=1,a_1=4,a_2=16,a_3=63$}$$

Answer 2

Here is essentially the same approach but with a convenient notation which helps to derive the recurrence relation.

We count the number $a(n)$ of valid strings from the alphabet $X=\{1,2,3,4\}$, i.e. strings which do not contain $344$ by partitioning them according to their matching length with the initial parts of the bad string $344$. \begin{align*} \color{blue}{a_n=a^{[\emptyset]}_n+a^{[4]}_n+a^{[44]}_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 $34\color{blue}{4}$, i.e. start with $1,2$ or $3$.

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

• The number $a^{[44]}_n$ counts the valid strings of length $n$ which do start with the two rightmost characters of the bad word $3\color{blue}{44}$, i.e. start with $\color{blue}{44}$.

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 $1,2$ or $3$ from the left it contributes to $a^{[\emptyset]}_{n+1}$. If it is appended by $4$ from the left it contributes to $a^{[4]}_{n+1}$.

• If a word counted by $a^{[4]}_n$ is appended by $1,2$ or $3$ from the left it contributes to $a^{[\emptyset]}_{n+1}$. If it is appended by $4$ from the left it contributes to $a^{[44]}_{n+1}$.

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

This relationship can be written as \begin{align*} \color{blue}{a^{[\emptyset]}_{n+1}}&\color{blue}{=3a^{[\emptyset]}_{n}+3a^{[4]}_{n}+2a^{[44]}_{n}}\tag{2}\\ \color{blue}{a^{[4]}_{n+1}}&\color{blue}{=a^{[\emptyset]}_{n}}\tag{3}\\ \color{blue}{a^{[44]}_{n+1}}&\color{blue}{=a^{[4]}_n+a^{[44]}_n}\tag{4} \end{align*}

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

We obtain for $n\geq 2$: \begin{align*} \color{blue}{a_{n+1}}&=a^{[\emptyset]}_{n+1}+a^{[4]}_{n+1}+a^{[44]}_{n+1}\tag{$ \to (1)$}\\ &=\left(3a^{[\emptyset]}_{n}+3a^{[4]}_{n}+2a^{[44]}_{n}\right)\\ &\qquad+a^{[\emptyset]}_{n}+\left(a^{[4]}_n+a^{[44]}_n\right)\tag{$\to (2),(3),(4)$}\\ &=4a^{[\emptyset]}_{n}+4a^{[4]}_{n}+3a^{[44]}_{n}\\ &=4a_n-a^{[44]}_{n}\tag{$\to (1)$}\\ &=4a_n-a^{[4]}_{n-1}-a^{[44]}_{n-1}\tag{$\to (4)$}\\ &=4a_n-a^{[\emptyset]}_{n-2}-\left(a^{[4]}_{n-2}-a^{[44]}_{n-2}\right)\tag{$\to (3),(4)$}\\ &\,\,\color{blue}{=4a_n-a_{n-2}}\tag{$\to (1)$} \end{align*} in accordance with an already given answer. We finally derive manually the starting values \begin{align*} \color{blue}{a_0=1,a_1=4,a_2=16} \end{align*}