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.

Find a recurrence relation for the number of ternary strings of length n that contain a pair of consecutive Os

The answer to this can be found quite easily to be: $$a_n=2a_{n-1}+2a_{n-2}+3^{n-2}\;.$$

Now I came across a similar question which asked this:

Find a recurrence relation for the number of ternary strings of length n that do NOT contain a pair of consecutive Os

I supposed that the answer would be the above answer subtracted from the total number os strings i.e $3^n$. But here on Pg 13 they're ending up with the same answer! They do start with an intuitive statement but they disregard it later.

What am I missing here?

share|improve this question
    
It might be worth checking a few small values of $n$ to see whether the solution given is correct. –  Gerry Myerson Dec 1 '12 at 5:03

2 Answers 2

Peter Capello lost track of what he was doing when he wrote up Exercise 30. Despite the wording of Exercise 30(a) and the first sentence of its ‘solution’, he actually solves the problem of finding a recurrence for the number of ternary strings of length $n$ that do contain the substring $00$. He continues this in Exercises 30(b) and 30(c).

The number $b_n$ of ternary strings of length $n$ that do not contain the substring $00$ is actually

$$\begin{align*} b_n&=3^n-a_n\\ &=3^n-\left(2a_{n-1}+2a_{n-2}+3^{n-2}\right)\\ &=3^n-\left(2\left(3^{n-1}-b_{n-1}\right)+2\left(3^{n-2}-b_{n-2}\right)+3^{n-2}\right)\\ &=3^n-\left(2\cdot3^{n-1}+3\cdot3^{n-2}-2b_{n-1}-2b_{n-2}\right)\\ &=2b_{n-1}+2b_{n-2}\;. \end{align*}$$

This recurrence is easily verified combinatorially: if $n\ge 2$, each string of length $n$ without $00$ is either such a string of length $n-1$ followed by a $1$ or $2$, or such a string of length $n-2$ followed by $10$ or $20$.

Added: By the way, the numbers $b_n$ have the closed form

$$a_n=\frac1{4\sqrt3}\left(\left(1+\sqrt3\right)^{n+2}-\left(1-\sqrt3\right)^{n+2}\right)\;.$$

This is easily derived by the usual methods, or one can simply consult OEIS A028859. The entry for the $a_n$ is OEIS A186244.

share|improve this answer
    
How do you obtain the closed form without OEIS? –  AlanH Mar 22 '13 at 23:52
    
If you don't mind, could you clarify or, rather, elaborate on your explanation after the equalities? –  AlanH Mar 22 '13 at 23:58
1  
@Alan: There are several techniques; perhaps the most elementary is explained in this PDF. It can also be done straightforwardly with generating functions, but they require a little more background machinery. –  Brian M. Scott Mar 23 '13 at 0:00
1  
@Alan: Take a string of length $n$ with no $00$ substring. If it ends in $1$ or $2$, the first $n-1$ digits must be good (i.e., not containing $00$) strings of length $n-1$. If it ends in $0$, the previous digit cannot be $0$, so it must end in $10$ or $20$, and what precedes that can be any good string of length $n-2$. –  Brian M. Scott Mar 23 '13 at 0:05
    
@Alan: You mean to deduce the recurrence from the problem statement? It’s a bit of an art, though practice certainly does help to get you pointed in the right direction. With string problems you should generally try to see how a good string (whatever that means in any given problem) of length $n$ can be formed from shorter good strings. More generally, you try to derive the stage $n$ objects in some natural way from objects at earlier stages, where natural way basically just means that you can count how many stage $n$ objects arise in that way from the stage whatever objects. –  Brian M. Scott Mar 23 '13 at 0:09

"the above answer subtracted from the total number of strings" doesn't make sense, since "the above answer" is an equation, and the number of strings is a number, and you can't subtract an equation from a number. Maybe what you mean is that if you let $b_n$ be the number of strings with no consecutive zeros then $b_n=3^n-a_n$. That is certainly true, and you can use it to get a recurrence. You have $a_n=3^n-b_n$, $a_{n-1}=3^{n-1}-b_{n-1}$, and $a_{n-2}=3^{n-2}-b_{n-2}$, so $$3^n-b_n=2(3^{n-1}-b_{n-1})+2(3^{n-2}-b_{n-2})+3^{n-2}$$ Hit this with lots of algebra to get $$b_n=2b_{n-1}+2b_{n-2}+3^n-2\cdot3^{n-1}-2\cdot3^{n-2}-3^{n-2}$$ and now see what you can do with those powers of $3$.

share|improve this answer

Your Answer

 
discard

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.