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!