The question is: Find a recurrence relation for number of ternary strings of length n that contain two consecutive zeros.
I know for ternary strings with length one, there are 0. For a length of 2, there is just 1 (00), and for a length of 3, there are 5 (000,001,002,100,200).
I did a similar problem, finding a relation for the number of bit strings of length n with two consecutive zeros: $$a_n = a_{n-1} + a_{n-2} + 2^{n-2}$$
Since you can add "1" to the end of all the $a_{n-1}$ strings, "10" to all the $a_{n-2}$ strings, and "00" any string of size $n-2$.
For the ternary string problem, I'm pretty sure you would replace the $2^{n-2}$ with $3^{n-2}$, but confused about the other terms of the relation. My guess is that it would have the coefficient $2$ in front of the other terms, since you can add either $1$ or $2$ to the end of $a_{n-1}$ and either $01$ or $02$ at the end of $a_{n-1}$.
So I believe the answer for the relation is: $$a_n = 2a_{n-1} + 2a_{n-2} + 3^{n-2}$$
How does that look?
Best Answer
If a ‘good’ ternary string of length $n$ ends in $00$, the first $n-2$ elements can be anything, so there are indeed $3^{n-2}$ such strings. If a good string of length $n$ ends in $1$ or $2$, its initial substring of length $n-1$ must be good; that accounts for $2a_{n-1}$ more good strings of length $n$, since each of the shorter strings can be extended with either $1$ or $2$. What hasn’t been counted? Good strings of length $n$ that end in a $10$ or $20$. Each of these must be an extension of a good string of length $n-2$, so there are $2a_{n-2}$ of them, and your conjecture is correct: $$a_n=2a_{n-1}+2a_{n-2}+3^{n-2}\;.$$