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. Find a 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.
I have no idea where to start. I've been stuck for some time. Any help is appreciated, Thanks.
 A: 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?
A: 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}$
A: Strings of length $n\ge 2$ fall in two classes; those that end with a double letter, and those that do not. There are $6a_{n-1}$  strings which do not end with a double letter (six choices for the end letter, anything but the previous), and $5a_{n-2}$ which do (five choices for the double, anything but $11$ or $22$), so
$$
a_{n}=6a_{n-1}+5a_{n-2},\qquad n\ge2.
$$
