Recurrence relation for substring Let us consider strings that are build up with symbols from the set $\{\&, \#, \$\}$ and digits from
the set $\{0, 1, 2, 3\}$. Let $a_n$ be the number of strings of length $n$ that contain the substring ’#1’.
Find a recurrence relation for $a_n$. Argue carefully.
My solution:
I have found 3 cases:

*

*The string doesn't end with '#', which means the '#1' has to be in the $n-1$ space. That gives me $6*a_{n-1}$.


*The string ends with '#1', which means we can have anything in the n-2 space. That gives me $7^{n-2}$.


*The string ends with only '#' (but not '#1') which means the string has to be in the n-2 space. That gives me $6*a_{n-2}$.
Now this would give me the recurrence relation: $6*a_{n-1}$ + $7^{n-2}$ + $6*a_{n-2}$.
I know that $a_{1} = 0$ and $a_{2}$ = 1. Then $a_{3}$ should be 13 according to my formula, but I know that that isn't correct (I brute calculated it and I know it should be 14).
Am I thinking this wrong?
 A: 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 invalid strings of length $n$ from the set $\{0,1,2,3,\&,\#,\$\}$, i.e. strings which do not contain $1\#$. We do so   by partitioning  them according to their matching length with the initial parts of   the  bad string $1\#$. The wanted number $b_n$ of valid strings of length $n$ is then given as
\begin{align*}
\color{blue}{b_n=7^n-a_n\qquad\qquad n\geq 1}\tag{1}
\end{align*}
We consider
\begin{align*}
\color{blue}{a_n=a^{[\emptyset]}_n+a^{[1]}_n}\tag{2}
\end{align*}

*

*The  number $a^{[\emptyset]}_n$ counts the invalid strings of  length  $n$   which do not start with the   rightmost character  of  the       bad   word $\#\color{blue}{1}$,  i.e.  start  with $0,2,3,\&,\#$ or $\$$.


*The  number $a^{[1]}_n$ counts the invalid strings of length  $n$  which do  start with the   rightmost character  of  the       bad   word $\#\color{blue}{1}$,  i.e.  $\color{blue}{1}$.
We  get a    relationship  between invalid strings of length $n$  with  those of length  $n+1$  as follows:

*

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


*If a word counted  by $a^{[1]}_n$ is appended by $0,2,3,\&$ or $\$$ from the left it contributes to $a^{[\emptyset]}_{n+1}$. If it is appended by $1$ from the left it contributes to $a^{[1]}_{n+1}$. Appending from the left by $\#$  is not allowed since then we have an invalid string starting with $\#1$.
This relationship can be written as
\begin{align*}
\color{blue}{a^{[\emptyset]}_{n+1}}&\color{blue}{=6a^{[\emptyset]}_{n}+5a^{[1]}_{n}}\tag{3}\\
\color{blue}{a^{[1]}_{n+1}}&\color{blue}{=a^{[\emptyset]}_n+a^{[1]}_n}\tag{4}
\end{align*}
We can now derive a recurrence relation from (2) - (4):

We obtain for $n\geq 2$:
\begin{align*}
\color{blue}{a_{n+1}}&=a^{[\emptyset]}_{n+1}+a^{[1]}_{n+1}\tag{$ \to (2)$}\\
&=\left(6a^{[\emptyset]}_{n}+5a^{[1]}_{n}\right)
+\left(a^{[\emptyset]}_{n}+a^{[1]}_n\right)\tag{$\to (3),(4)$}\\
&=7a^{[\emptyset]}_{n}+6a^{[1]}_{n}\\
&=7a_n-a^{[1]}_{n}\tag{$\to  (2)$}\\
&=7a_n-\left(a^{[\emptyset]}_{n-1}+a^{[1]}_{n-1}\right)\tag{$\to  (4)$}\\
&\,\,\color{blue}{=7a_n-a_{n-1}}\tag{$\to (2)$}
\end{align*}
We derive using (1) the wanted recurrence relation for $b_n$ as
\begin{align*}
\color{blue}{b_{n}}&=7^{n}-a_{n}\\
&=7^{n}-7a_{n-1}+a_{n-2}\\
&=7^{n}-7\left(7^{n-1}-b_{n-1}\right)+(7^{n-2}-b_{n-2})\\
&\color{blue}{=7^{n-2}+7b_{n-1}-b_{n-2}\qquad\qquad\qquad\qquad\qquad n\geq 3}\\
\color{blue}{b_1}&\color{blue}{=0}\\
\color{blue}{b_2}&\color{blue}{=1}\\
\end{align*}

The first few values of the wanted recurrence relation are
\begin{align*}
\color{blue}{(b_n)_{n\geq 1}=\{0,1,14,146,1\,351,11\,712,\ldots\}}
\end{align*}
