Recurrence relation for the number of strings of length $n$ over the alphabet $\{1, 2,3,4,5,6,7\}$ such that there are no consecutive $1$'s or $2$'s.

Make coupled recurrences, one for the number of good strings of length $n$ that do not end in $1$ or $2$ and one for the number of good strings that do end in $1$ or $2$. Given the number of each, how many strings of length $n+1$ of each type are there?

Building on Ross's hint.

Let $a_n$ be the number of good strings of length $n$

Let $b_n$ be the number of good strings of length $n$ which do not end in a $1$ or $2$

Let $c_n$ be the number of good strings of length $n$ which end in $1$

Let $d_n$ be the number of good strings of length $n$ which end in $2$

This gives the recurrence $a_n=b_n+c_n+d_n$

Obviously, $b_n = 5a_{n-1}$

Also we have $c_n=b_{n-1}+d_{n-1}$ because the right hand side of the equation is the number of good strings of length $n-1$ which do not end in a $1$.

Finally, $d_n=b_{n-1}+c_{n-1}$ because the right hand side of the equation is the number of good strings of length $n-1$ which do not end in a $2$

Substituting for $b_n$, $c_n$, $d_n$ in the first equation the equations we get, $a_n = 5a_{n-1}+b_{n-1}+d_{n-1}+b_{n-1}+c_{n-1}$ = $5a_{n-1}+b_{n-1}+a_{n-1}$ = $6a_{n-1}+5a_{n-2}$

Therefore, $a_n=6a_{n-1}+5a_{n-2}$