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 ?
Best Answer
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.