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}\;.$$
I am learning this right now...
I find it helpful to think of it this way:
building from the end of the string,
___1 = g(n-1) combinations; splits into:
- ___11 = g(n-2)
- ___01 = g(n-2)
- ___21 = g(n-2)
since they are all legal strings, we keep all of them, so you add g(n-1) to your recursion.
___0 = g(n-1) combinations; splits into:
- ___00 = g(n-2)
- ___10 = g(n-2)
- ___20 = g(n-2), All legal: add g(n-1) to recursion
___2 = g(n-1) combinations; splits into:
Summing everything together, you note that 02 contributes: g(n-2) - g(n-3), and, having already established, by virtue of the ternary property, that g(n-1) = 3g(n-2), you get that __2's contribution is g(n-1) - g(n-3).
Summing everything together, you have:
$$
3g(n-1) - g(n-3) = g(n)
$$
And that just makes sense to me, because this is a tree we are talking about...and this explanation unfolds like a breadth first search reinterpreted as a recursion. Super intuitive.
Best Answer
Peter Capello lost track of what he was doing when he wrote up Exercise 30. Despite the wording of Exercise 30(a) and the first sentence of its ‘solution’, he actually solves the problem of finding a recurrence for the number of ternary strings of length $n$ that do contain the substring $00$. He continues this in Exercises 30(b) and 30(c).
The number $b_n$ of ternary strings of length $n$ that do not contain the substring $00$ is actually
$$\begin{align*} b_n&=3^n-a_n\\ &=3^n-\left(2a_{n-1}+2a_{n-2}+3^{n-2}\right)\\ &=3^n-\left(2\left(3^{n-1}-b_{n-1}\right)+2\left(3^{n-2}-b_{n-2}\right)+3^{n-2}\right)\\ &=3^n-\left(2\cdot3^{n-1}+3\cdot3^{n-2}-2b_{n-1}-2b_{n-2}\right)\\ &=2b_{n-1}+2b_{n-2}\;. \end{align*}$$
This recurrence is easily verified combinatorially: if $n\ge 2$, each string of length $n$ without $00$ is either such a string of length $n-1$ followed by a $1$ or $2$, or such a string of length $n-2$ followed by $10$ or $20$.
Added: By the way, the numbers $b_n$ have the closed form
$$a_n=\frac1{4\sqrt3}\left(\left(1+\sqrt3\right)^{n+2}-\left(1-\sqrt3\right)^{n+2}\right)\;.$$
This is easily derived by the usual methods, or one can simply consult OEIS A028859. The entry for the $a_n$ is OEIS A186244.