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!
Best Answer
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.