# Homework Help: 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.