Finding recurrence relation that contain and do not contain $122$ in the alphabet of $(0,1,2,3,4)$ Lets consider the $n-$ strings over the alphabet $\color{purple}{\{0,1,2,3,4\}}$ that
$\color{blue}{a-)}$ do not contain the substring $\color{green}{122}$ such that $1334211112$ is allowed but $..44311 $$\color{red}{122}$ $344..$ is not allowed.
$\color{blue}{b-)}$ contain the substring $\color{green}{122}$
I am trying to find the recurrence relation of $n$ strings that satisfies the desired conditions respectively.I found recurrence relations but i am not sure whether they are true or not .
$\color{BROWN}{SOLUTION:}$
$\color{blue}{a-)}$ We know that this $n$ lenght strings will end up with either $0$ or $1$ or $2$ or $3$ or $4$.
Lets say that the  string ends  with $0$ and does not contain $122$ , so there are $a_{n-1}$ such strings.
Lets say that the  string ends  with $1$ and does not contain $122$ , so there are $a_{n-1}$ such strings.
Lets say that the  string ends  with $2$ and does not contain $122$ , so there are $a_{n-1}$ such strings.
Lets say that the  string ends  with $3$ and does not contain $122$ , so there are $a_{n-1}$ such strings.
Lets say that the  string ends  with $4$ and does not contain $122$ , so there are $a_{n-1}$ such strings.
So, there are $5a_{n-1}$ such strings that do not contain $122$ , but let us think about the string which end with $2$ and do not contain $122$. It has $a_{n-1}$ string that do not have $122$ , but this $a_{n-1}$ string might end with $12$. Because of this, we must subtract the sequence which end up with $2$ and have a substring with lengh $n-1$ but end with $12$.
Hence , the solution is $a_n=5a_{n-1}-a_{n-3}$
$\color{blue}{b-)}$ We know that this $n$ lenght strings will end up with either $0$ or $1$ or $2$ or $3$ or $4$.
Lets say that the  string ends  with $0$ and  contains $122$ , so there are $a_{n-1}$ such strings.
Lets say that the  string ends  with $1$ and  contains $122$ , so there are $a_{n-1}$ such strings.
Lets say that the string ends  with $02$ and  contains $122$ , so there are $a_{n-2}$ such strings.
Lets say that the  string ends  with $12$ and  contains $122$ , so there are $a_{n-2}$ such strings.
Lets say that the  string ends  with $022$ and  contains $122$ , so there are $a_{n-3}$ such strings.
Lets say that the  string ends  with  $122$ , so there are $5^{n-3}$ such strings.
Lets say that the  string ends  with $322$ and  contains $122$ , so there are $a_{n-3}$ such strings.
Lets say that the  string ends  with $422$ and  contains $122$ , so there are $a_{n-3}$ such strings.
Lets say that the  string ends  with $32$ and  contains $122$ , so there are $a_{n-2}$ such strings.
Lets say that the string ends  with $42$ and  contains $122$ , so there are $a_{n-2}$ such strings.
Lets say that the string ends  with $3$  contains $122$ , so there are $a_{n-1}$ such strings.
Lets say that the  string ends  with $4$  contains $122$ , so there are $a_{n-1}$ such strings.
$\therefore a_n=4a_{n-1}+4a_{n-2}+3a_{n-3}+5^{n-3}$
Is my solution correct ? Moreover , if you know another approach to this solution , can you share your knowledge with me ?
What's more , do you know any book or website to find these types of exercises to improve myself ?
 A: The first is correct.  You claim that you can take any $n-1$ string and add any character to it (which gives $5a_{n-1}$) except the ones that end in $122$ (which is the subtraction of $a_{n-3})$. You should give starting conditions $a_0=1,a_1=5,a_2=25$
For the second it would be better not to reuse the notation $a_n$.  If we call the number of $n$ strings that include $122$ somewhere $b_n$ we clearly have $a_n+b_n=5^n$.  If you don't mind coupled recurrences this gives $b_n=5b_{n-1}+a_{n-3}$.  Your statement that the string ends with $122$ gives $2^{n-3}$ is wrong.  It should be $5^{n-3}$.  You also miss strings that end in $222$, which changes the $3$ coefficient to $4$.  Unfortunately the result, $b_n=4(b_{n-1}+b_{n-2}+b_{n-3})+5^{n-3}$ misses strings like $1222$.  It doesn't end in $122$ so it is missed by the last term and it doesn't have $122$ somewhere before your additions.
A: Here we derive a recurrence relation for (a) and (b) based upon a generating function approach, the so-called Goulden-Jackson Cluster Method.
Case (a):

We consider the set of words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{0,1,2,3,4\}$$ and the set $B=\{122\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $A(z)$ with the coefficient of $z^n$ being  the number of wanted words of length $n$ and derive from it the currence relation.

According to the paper (p.7) the generating function $A(z)$  is
\begin{align*}
A(z)=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\tag{1}
\end{align*}
with $d=|\mathcal{V}|=5$, the size of the alphabet and $\mathcal{C}$ the weight-numerator of bad words with
\begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[122])
\end{align*}
We calculate according to the paper
\begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[122])&=-z^3\\
\end{align*}

It    follows
\begin{align*}
\color{blue}{A(z)}&=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\\
&\,\,\color{blue}{=\frac{1}{1-5z+z^3}}\tag{1}\\
\end{align*}

We recall if a generating function has a representation as rational function of the form
\begin{align*}
A(z)=\sum_{n=0}^\infty a_n z^n=\frac{P(z)}{Q(z)}
\end{align*}
with $P(z), Q(z)$ polynomials, $\deg Q=q>\deg P$ and
\begin{align*}
Q(z)=1+\alpha_1 z+\alpha_2 z^2+\cdots + \alpha_q z^q
\end{align*} then the coefficients $a_n$ follow the recurrence relation
\begin{align*}
a_{n+q}+\alpha_1 a_{n+q-1}+\alpha_2 a_{n+q-2}+\cdots +\alpha_q a_{n}=0\qquad\qquad n\geq 0
\end{align*}
See for instance theorem 4.1.1 in Enumerative Combinatorics, Vol. I by R. P. Stanley.

Thanks to this theorem we can derive the recurrence relation from (1) as
\begin{align*}
a_{n+3}-5a_{n+2}+a_{n}=0\qquad\qquad n\geq 0
\end{align*}
resp. by shifting the indices we get
\begin{align*}
\color{blue}{a_n}&\color{blue}{=5a_{n-1}-a_{n-3}}\qquad\qquad n\geq 3\tag{2}\\
\color{blue}{a_0}&\color{blue}{=1, a_1=5, a_2=25}
\end{align*}
The initial conditions of the recurrence relation (2) follow immediately, since the number of all words of length $n$ from the alphabet $\mathcal{V}=\{0,1,2,3,4\}$ is $5^n$ and the restriction due to the bad word $122$ becomes effective starting with $n=3$ where $a_3=5^3\color{blue}{-1}=124$.

Case (b):
We derive a recurrence relation for all words of length $n\geq 0$ built from the alphabet $$\mathcal{V}=\{0,1,2,3,4\}$$ which do contain the word $122$ with the help from case (a).

Since the number of all words of length $5$ built from the alphabet $\mathcal{V}$ is $5^n$, a generating function $B(z)$ is
\begin{align*}
\color{blue}{B(z)}&=\sum_{n=0}^\infty b_nz^n=\sum_{n=0}^\infty \left(5^n-a_n\right)z^n\\
&=\sum_{n=0}^\infty 5^nz^n-A(z)\\
&=\frac{1}{1-5z}-\frac{1}{1-5z+z^3}\\
&\,\,\color{blue}{=\frac{z^3}{1-10z+25z^2+z^3-5z^4}}\tag{3}
\end{align*}

Thanks to the the theorem above we find from (3) the recurrence relation
\begin{align*}
b_{n+4}-10b_{n+3}+25b_{n+2}+b_{n+1}-5b_n=0\qquad\qquad n\geq 0
\end{align*}
resp. by shifting the indices we get

\begin{align*}
\color{blue}{b_n}&\color{blue}{=10b_{n-1}-25b_{n-2}-b_{n-3}+5b_{n-4}}\qquad\qquad n\geq 4\\
\color{blue}{b_0}&\color{blue}{=b_1=b_2=0}\\
\color{blue}{b_3}&\color{blue}{=1}
\end{align*}
The initial conditions might follow immediately or can be derived from the relation $b_n=5^n-a_n$.

A: Here we give an answer for the part (a) which can be seen as supplement to OPs nice solution. We use a convenient notation which is helpful to derive the wanted recurrence relation.

We count the number $a_n$ of valid binary strings, i.e. strings which do not contain $122$   by partitioning  them according to their matching length with the initial parts of  the  bad string $122$.
\begin{align*}
\color{blue}{a_n=a^{[0134]}_n+a^{[2]}_n+a^{[22]}_n}\tag{1}
\end{align*}

*

*The  number $a^{[0134]}_n$ gives the number of valid words of length  $n$ with left-most character in $\{0,1,3,4\}$.


*The  number $a^{[2]}_n$ counts the valid strings of length  $n$  which  start with left-most character $2$, which is the rightmost character  of  the  bad   word $12\color{blue}{2}$.


*The  number $a^{[22]}_n$ counts the valid strings of length   $n$   which  have as left-most characters $22$, which are the two right-most characters  of  the       bad   word $1\color{blue}{22}$.

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

*

*If a word counted  by $a^{[0134]}_n$ is appended with a character from $\{0,1,3,4\}$ from the left, it contributes to $a^{[0134]}_{n+1}$. If it is appended by $2$ from the left it contributes to $a^{[2]}_{n+1}$.


*If a word counted  by $a^{[2]}_n$ is appended with a character from $\{0,1,3,4\}$ from the left, it contributes to $a^{[0134]}_{n+1}$. If it is appended by $2$ from the left it contributes to $a^{[22]}_{n+1}$.


*If a word counted  by $a^{[22]}_n$ is appended with a character from $\{0,1,3,4\}$ from the left, it contributes to $a^{[0134]}_{n+1}$. Appending from the left by $1$  is not allowed since then we have an invalid word starting with $122$.

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

Note that we have $5$ characters $0,1,2,3,4$ to consider which can be appended to the left and the equations (2) - (4) show $5$ times $a^{[0134]}_{n},a^{[2]}_{n}$ and $4$ times $a^{[22]}_n$ indicating that all different cases are considered.
We can  now derive a recurrence relation from (1) - (4):

We obtain for $n\geq 3$:
\begin{align*}
\color{blue}{a_{n+1}}&=a^{[0134]}_{n+1}+a^{[2]}_{n+1}+a^{[22]}_{n+1}\tag{$ \to (1)$}\\
&=\left(4a^{[0134]}_{n}+4a^{[2]}_{n}+3a^{[22]}_{n}\right)\\
&\qquad +\left(a^{[0134]}_{n}\right)+\left(a^{[2]}_n+a^{[22]}_n\right)\tag{$\to (2),(3),(4)$}\\
&=5a^{[0134]}_{n}+5a^{[2]}_{n}+4a^{[22]}_{n}\\
&=5a_n-a^{[22]}_{n}\tag{$\to (1)$}\\
&=5a_n-\left(a^{[2]}_{n-1}+a^{[22]}_{n-1}\right)\tag{$\to  (4)$}\\
&=5a_n-\left(a^{[0123]}_{n-2}\right)-\left(a^{[2]}_{n-2}+a^{[22]}_{n-2}\right)\tag{$\to  (3),(4)$}\\
&\,\,\color{blue}{=5a_n-a_{n-2}}\tag{$\to (1)$}
\end{align*}
in accordance with OP's result.

A: Taking strings containing $122$ as "qualifying", I identify $4$ states to track for each length of string:

*

*General non-qualifying strings that doesn't end in $1$ or $12$, quantity "$G$"

*Non-qualifying strings that end in $1$, quantity "$P_1$"

*Non-qualifying strings that end in $12$, quantity "$P_2$"

*Qualifying strings, quantity "$Q$"

Then the transition from one length to the next looks like this:

that is

*

*$G(n+1) = 4G(n)+3P_1(n)+3P_2(n)$

*$P_1(n+1) = G(n)+P_1(n)+P_2(n)$

*$P_2(n+1) = P_1(n)$

*$Q(n+1) = P_2(n)+5Q(n)$
Non-qualifying strings in general are $G+P_1+P_2$, quantity "NQ", so $P_1(n) = NQ(n-1)$
Then substituting $P_1(n-1) = NQ(n-2)$ for $P_2(n)$ we have

*

*$G(n+1) = 4G(n)+3P_1(n)+3P_2(n) = 4NQ(n)-NQ(n-1)-NQ(n-2)$

*$P_1(n+1) = NQ(n)$

*$P_2(n+1) = NQ(n-1)$

*$\color{#0b2}{NQ(n+1) = 5NQ(n) - NQ(n-2)}$

*$\color{#0b2}{Q(n+1) = 5Q(n) + NQ(n-2)}$
As you might expect, the number of qualifying strings gradually catches up to the non-qualifying strings and overtakes at $n=87$.
