Recurrence Relation for Two Consecutive 0s in Ternary Strings

[Mr Davis 97]

Homework Statement

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

Homework Equations

The Attempt at a Solution

Let $a_n$ count the number of ternary stings of length n that contain two consecutive 0s. Then, we can split the total number into mutually exclusive cases. If we start with 1 or 2, then we have $a_{n-1}$ in both cases. If we start with 01 or 02, then we have $a_{n-2}$ in both cases. If we start with 00, then we have $3^{n-2}$ possibilities for the other strings, since we already have two consecutive zeroes. Thus $a_n = 2a_{n-1} + 2a_{n-2} + 3^{n-2}$.

However, apparently the solution is $a_n = 2a_{n-1} + 2a_{n-2} + 2^{n-2}$. Is this correct or is mine correct?

 

[andrewkirk]

Perhaps they mean exactly one instance of 00, rather than one or more instances of 00. Under the latter (former) interpretation you (they) are correct.

 

[haruspex]

Perhaps they mean exactly one instance of 00, rather than one or more instances of 00. Under the latter (former) interpretation you (they) are correct.

No, it still doesn't make the book answer correct. Even though there must be no more pairs of consecutive zeroes, there can still be isolated ones.