Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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. – André Nicolas Dec 9 '12 at 23:43
up vote 0 down vote accepted

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

share|cite|improve this 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.

share|cite|improve this answer
I'm still a bit confused though. Since there 3 choices for the first digit, and 3 choices for the second, there should be 9 different 2-digit sequences that I can prepend to a $(n-3)$ sequence. I know that you can't prepend $01$, so that is why I subtract 1 to get 8 different $(n-3)$ sequences. – user1526710 Dec 10 '12 at 0:05
@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.) – Brian M. Scott Dec 10 '12 at 0:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.