1
$\begingroup$

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!

  • 1
    Yours is not the same. The numbers for $1$, $2$, $3$ are easy to find they are $0,0,1$. Yours then predicts $2$ at $n=4$. The official answer predicts $3$, which you can see is right.2012-12-09

2 Answers 2

0

Which $n$-digit sequences beginning with $00$ do not begin in $0012$? Is it the set of all $(n-2)$-digit sequences?

1

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.

  • 1
    @user1526710: But you can’t prepend $01$ to all $a_{n-3}$ of the acceptable sequences of length $n-3$: you can prepend it only to those that don’t start with $2$. Thus, your $8a_{n-3}$ adds too many $(n-2)$-sequences beginning with $01$. (There are obviously other problems, since your formula consistently yields numbers that are too small, not too large, but this was the easiest one to explain.)2012-12-10