2
$\begingroup$

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

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 $0$s

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?

  • 0
    It might be worth checking a few small values of $n$ to see whether the solution given is correct.2012-12-01

2 Answers 2

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.

  • 0
    @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.2013-03-23
0

"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$.