Recurrence relation for the number of $n$-digit ternary sequences with no consecutive $1$s or $2$s 
Find the recurrence relation for the number of $n$-digit ternary sequences with no consecutive $1$'s or $2$'s.

The solution is 
$$
a_n = a_{n-1} + 2a_{n-2} + 2a_{n-3} + 2a_{n-4} + \dots. \tag1
$$
I've thought about this for quite some time and I can't really understand it. I feel like I'm making up my reasoning to fit the solution; rather than understanding why it really is in the above form. 
Can someone please explain this combinatorially?
 A: Take a good $n$-digit sequence, i.e., one with no $11$ or $22$ subsequence. 


*

*If it ends in $0$, the initial $(n-1)$-subsequence is good, so there are $a_{n-1}$ good $n$-sequences ending in $0$. 

*If it ends in $1$, it must actually end in either $01$ or $21$, and if it ends in $2$, it must actually end in either $02$ or $12$. A $0$ can follow any good sequence, so each good $(n-2)$-sequence gives rise to two good $n$-sequences, one ending in $1$ and one ending in $2$, by appending $01$ or $02$, respectively. Since there are $a_{n-2}$ good $(n-2)$-sequences, that accounts for the $2a_{n-2}$ good $n$-sequences ending in $01$ or $02$. That still leaves the $n$-sequences ending in $21$ or $12$ to be counted.

*If the $n$-sequence ends in $21$, it must actually end in $021$ or $121$; similarly, if it ends in $12$, it must actually end in $012$ or $212$. The $021$ and $012$ cases can now be handled as before: a $0$ can follow any good sequence, so there are $a_{n-3}$ good $n$-sequences ending in $021$ and another $a_{n-3}$ ending in $012$; between them they account for another $2a_{n-3}$ good $n$-sequences, but the $n$-sequences ending in $121$ and $212$ remain to be accounted for.
The pattern should now be pretty clear. In fact we can do better. Suppose that the last $0$ in a given $n$-sequence is in the $k$-th position, where $k<n$. It can follow any of the $a_{k-1}$ good $(k-1)$-sequences, and it must be followed by either $1212\dots$ or $2121\dots$. Thus, for each $k<n$ there are $2a_{k-1}$ good $n$-sequences having their last $0$ in the $k$-th position.
A: As is common in problems of this type, it is useful to define other related sequences. Call a sequence with no two consecutive $1$'s or $2$'s good.
Let $p_n$ be the number of good  sequences of length $n$ that end in $0$, $q_n$ the number that end in $1$, and $r_n$ the number that end in $2$.
We have the obvious recurrence $p_{n}=p_{n-1}+q_{n-1}+r_{n-1} =a_{n-1}$. 
Also, $q_{n}=p_{n-1} +r_{n-1}$, and $r_{n}=p_{n-1}+q_{n-1}$. This is because, for example, to make a good sequence of length $n$ that ends in $1$, we take a good sequence of length $n-1$ that doesn't end in $1$, and append a $1$.
Add up. We get $a_{n}=2a_{n-1}+p_{n-1}$.
But $p_{n-1}=a_{n-2}$. So we end up with the recurrence
$$a_{n}=2a_{n-1}+a_{n-2}.$$
From this nice recurrence we can get a closed form. We can also get the recurrence of the post.
For assume by way of induction hypothesis that for a certain number $k$, we have
$$a_k=a_{k-1}+2a_{k-2}+2a_{k-3}+\cdots$$
Then 
$$a_{k+1}=2a_k +a_{k-1}=a_k+(a_{k-1}+a_k)=a_k+(2a_{k-1}+2a_{k-2}+2a_{k-3}+\cdots).$$
A: Call the number of sequences that interest you that end in 0 $a_n$, if they end in 1 $b_n$, $c_n$ if they end in 2, and $d_n$ for ending in 3. Then clearly:
$$
a_0 = b_0 = c_0 = d_0 = 1
$$
Now think how a sequence that ends in 0 can be built: Add a 0 to any of the others, so $a_{n + 1} = a_n + b_n + c_n + d_n$. To make a sequence ending in 1, anything except a sequence ending in 1 can come before, so it is $b_{n + 1} = a_n + c_n + d_n$. Continuing the same way:
$$
\begin{align*}
a_{n + 1} &= a_n + b_n + c_n + d_n \\
b_{n + 1} &= a_n + c_n + d_n \\
c_{n + 1} &= a_n + b_n + d_n \\
d_{n + 1} &= a_n + b_n + c_n + d_n 
\end{align*}
$$
This setup serves for any restrictions you care to set up.
Now define generating functions:
$$
\begin{align*}
A(z) &= \sum_{n \ge 0} a_n z^n \\
B(z) &= \sum_{n \ge 0} b_n z^n \\
C(z) &= \sum_{n \ge 0} c_n z^n \\
D(z) &= \sum_{n \ge 0} d_n z^n
\end{align*}
$$
This gives the system of equations:
$$
\begin{align*}
\frac{A(z) - 1}{z} &= A(z) + B(z) + C(z) + D(z) \\
\frac{B(z) - 1}{z} &= A(z) + C(z) + D(z) \\
\frac{C(z) - 1}{z} &= A(z) + B(z) + D(z) \\
\frac{D(z) - 1}{z} &= A(z) + B(z) + C(z) + D(z)
\end{align*}
$$
By sheer luck, the values we are interested in are just the $a_{n + 1}$. Solving the system of equations we get:
$$
A(z) = \frac{1 + z}{1 - 3 z - 2 z^2}
$$
This can be split into (very ugly) partial fractions, and expand the resulting geometric series:
$$
a_n = - \frac{\sqrt{17} - 1}{\sqrt{17} (\sqrt{17} + 3)}
          \cdot \left( - \frac{4}{\sqrt{17} + 3} \right)^n
      + \frac{\sqrt{17} + 1}{\sqrt{17} (\sqrt{17} - 3)}
          \cdot \left(\frac{4}{\sqrt{17} - 3} \right)^n
$$
(this would need some more cleanup, sorry for the mess).
A: I don't really think you need an infinite recurrence equation. I'm pretty confident that the following solves the question with a recurrence relation with  just 2 terms.
Ternary sequences can start with $0$, $1$, or $2$, so we need cases


*

*$3a_{n-1}$  Starts with $0$, $1$, or $2$, followed by an $n-1$ length sequence. This includes some invalid sequences so we subtract them later

*$-a_{n-2}$  Has two a $1$s in a row, so follow with a $n-2$ length sequence. (We subtract since it's invalid)

*$-a_{n-2}$  Has two a $2$s in a row, so follow with a $n-2$ length sequence. (Again, subtract since it's invalid)


Combining the cases we get
$$a_n=3a_{n-1}-2a_{n-2}$$
Base cases
$a_0=1$  (1 way to have a sequence of nothing)
$a_1=3$  (3 since there's no way to get an illegal sequence using only 1 digit & there are 3 digits)
$$$$
Does this work? I think it does, but let's verify for $n=2$
$a_2=3a_{2-1}-2a_{2-2}$
$=3a_1-2a_0$
$=3*3-2*1$  (plugging in bases cases)
$=9-2$
$=7$
Verifying combinatorially by counting
$a_2=$ all sequences of length $2$ minus the invalid ones ($11$ and $22$)
$a_2=3^2-1-1$  (3 possible digits in each space, minus 2 invalid)
$=9-2$
$=7$
Or you could literally write out the possible sequences of length 2 & count them up excluding the invalid sequences $11$ and $22$
$00$, $01$, $02$, $10$, $12$, $20$, $21$
I count $7$ valid sequences
