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?

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).
