Different recurrence relations that model the same problem I'm trying to solve the following counting problem, but my answer is different from the textbook's:
Find a recurrence relation for the number of n-digit ternary sequences that have the pattern "012" occurring for the first time at the end of the sequence. 
The textbook's solution is that you have $a_{n-1}$ ways for n-1 digits, so you can add a 0,1,or 2 in front to get a total of $3a_{n-1}$ ways.  If you add 0 to n-1 digit sequence, you need to subtract the number of sequences of n-1 digits that start with 12, which is $a_{n-3}$, so the final answer is $a_n = 3a_{n-1} - a_{n-3}$.
My solution is that you can add a 1 or 2 in front of the n-1 digit sequence (to get $2a_{n-1}$).  When adding a 0 in front, there are 8 out of 9 possible sequences of n-1 digits that start with 12, so I got $8a_{n-3}$ ways.  So my final solution is $a_n = 2a_{n-1} + 8a_{n-3}$
Is my answer the same as the textbook's, and if not, what is wrong with my reasoning?  Thanks!
 A: The two are clearly not the same. They might, however, generate the same sequence of numbers. This is easily checked. Clearly $a_0=a_1=a_2=0,a_3=1$, and $a_4=3$. Neither recurrence gives the correct result for $a_3$, so there must be an unstated assumption that $n\ge 4$. Assuming initial values of $a_1=a_2=0$ and $a_3=1$, the two recurrences yield the following results:
$$\begin{array}{rcc}
n:1&2&3&4&5&6\\
3a_{n-1}-a_{n-3}:0&0&1&3&9&26\\
2a_{n-1}+8a_{n-3}:0&0&1&2&4&16
\end{array}$$
Clearly they do not yield the same sequence.
It’s perfectly true that if you have an acceptable sequence of length $n-1$, you can safely prepend $1$ or $2$; that does indeed give you $2a_{n-1}$ acceptable sequences of length $n$. It’s also true that you can prepend $0$ if and only if the $(n-1)$-sequence does not begin with $12$. However, your assumption that each of the other two-digit combinations can be followed by any of the $a_{n-3}$ acceptable sequences of length $n-3$ is false. For example, there are acceptable $(n-3)$-sequences that begin with $2$, and you can’t prepend $01$ to those sequences to get an acceptable $(n-1)$-sequence.
A: Which $n$-digit sequences beginning with $00$ do not begin in $0012$? Is it the set of all $(n-2)$-digit sequences?
