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?

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.
