# Recurrence relation

1. Nov 16, 2016

### Mr Davis 97

1. The problem statement, all variables and given/known data
Find a recurrence relation for the number of ternary strings of length n that contain two consecutive 0s.

2. Relevant equations

3. 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?

2. Nov 16, 2016

### 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.

3. Nov 17, 2016

### haruspex

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.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted