Recurrence for the number of ternary strings of length $n$ that contain either two consecutive $0$s or two consecutive $1$s I attempted this problem and this is what I have so far:
First, I considered the possible "cases". 
If the string starts with $00$ or $11$, then the rest can be anything so there are  $2\cdot 3^{n-2}$ such strings.
If the string starts with $2$, then there are $n-1$ strings that contain two consecutive $0$s or $1$s.
If the string starts with $22$, then there are $n-2$ strings that contain two consecutive $0$s or $1$s.
I came up with the recurrence relation:
$$a_n=a_{n-1}+a_{n-2}+2\cdot 3^{n-1}.$$
However, the solution in my textbook says it is actually
$$a_n=2a_{n-1}+a_{n-2}+2\cdot 3^{n-2}.$$
I can't seem to figure out why $a_{n-1}$ is multiplied by two. 
 A: 
We can derive the recurrence relation for $a_n$ as follows:
  
  
*
  
*00|11:  A string may start with either $00$ or $11$ leaving $\color{blue}{2\cdot 3^{n-2}}$ ways for the remaining substring of length $n-2$.
  
*22: A string  may start with $22$ leaving $\color{blue}{a_{n-2}}$ ways for the remaining substring of length $n-2$.
In all the other cases the string starts
  
  
*
  
*0(1|2): either with $0$ followed by $1$ or $2$ 
  
*1(0|2):  or with $1$ followed by $0$ or $2$
  
*2(0|1): or with $2$ followed by $0$ or $1$.
In each of these three cases the first character is followed by one of two characters leaving $\color{blue}{2a_{n-1}}$ ways for the remaining substring of length $n-1$.

We conclude a recurrence relation for $a_n$ is
\begin{align*}
a_n&=2a_{n-1}+a_{n-2}+3\cdot 2^{n-2}\qquad\qquad n\geq 4\\
a_2&=2\\
a_3&=10
\end{align*}
The base cases $a_2=2$ and $a_3=10$ can be manually verified by
\begin{align*}
&n=2:\qquad 00,11\\
&n=3:\qquad 000,001,002,011,100,110,111,112,200,211
\end{align*}
