Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The question is: Find a recurrence relation for number of ternary strings of length n that contain two consecutive zeros.

I know for ternary strings with length one, there are 0. For a length of 2, there is just 1 (00), and for a length of 3, there are 5 (000,001,002,100,200).

I did a similar problem, finding a relation for the number of bit strings of length n with two consecutive zeros: $$a_n = a_{n-1} + a_{n-2} + 2^{n-2}$$

Since you can add "1" to the end of all the $a_{n-1}$ strings, "10" to all the $a_{n-2}$ strings, and "00" any string of size $n-2$.

For the ternary string problem, I'm pretty sure you would replace the $2^{n-2}$ with $3^{n-2}$, but confused about the other terms of the relation. My guess is that it would have the coefficient $2$ in front of the other terms, since you can add either $1$ or $2$ to the end of $a_{n-1}$ and either $01$ or $02$ at the end of $a_{n-1}$.

So I believe the answer for the relation is: $$a_n = 2a_{n-1} + 2a_{n-2} + 3^{n-2}$$

How does that look?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

If a ‘good’ ternary string of length $n$ ends in $00$, the first $n-2$ elements can be anything, so there are indeed $3^{n-2}$ such strings. If a good string of length $n$ ends in $1$ or $2$, its initial substring of length $n-1$ must be good; that accounts for $2a_{n-1}$ more good strings of length $n$, since each of the shorter strings can be extended with either $1$ or $2$. What hasn’t been counted? Good strings of length $n$ that end in a $10$ or $20$. Each of these must be an extension of a good string of length $n-2$, so there are $2a_{n-2}$ of them, and your conjecture is correct: $$a_n=2a_{n-1}+2a_{n-2}+3^{n-2}\;.$$

share|improve this answer
fixed the typos –  Pat Needham Apr 4 '12 at 2:21
@Pat: And I’ve removed the parenthetical note. –  Brian M. Scott Apr 4 '12 at 2:26
thank you very much for confirming my conjecture –  Pat Needham Apr 4 '12 at 2:36

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.