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