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

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?

• for $n=4$ , your answer is $3\times (63+16+4)=249$ , but the real answer is $248$ with brutal force such that $4^4 -(a344 +344a)$ where $a$ can be any number in the alphabet Commented Jun 26, 2022 at 9:05

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

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*}