Recurrence relation for number of ternary strings that contain two consecutive zeros 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?

Let us count the number of strings $a_n$ that do not contain $00$ as a substring. The required number of strings that contain $00$ is $3^n - a_n$.
Let us call a string that does not contain $00$ as good. Let $x_n, y_n, z_n$ be the number of good strings of length $n$ that end with $0, 1, 2$ respectively. Clearly,
\begin{align*}
x_{n+1} &= y_n + z_n \\
y_{n+1} &= x_n + y_n + z_n \\
z_{n+1} &= x_n + y_n + z_n
\end{align*}
Thus 
\begin{align*}
y_n = z_n, \qquad x_{n+1} = 2y_n, \qquad y_{n+1} = x_n + 2y_n
\end{align*}
and $y_n$ satisfies the recurrence
$y_{n+1} - 2y_n - 2y_{n-1} = 0$. The characteristic roots are $1 \pm \sqrt{3}$ and 
$$y_n = A(1+\sqrt{3})^n + B(1-\sqrt{3})^n$$
where $A, B$ are constants. Since $y_2 = 3$ and $y_3 = 8$ we get 
$$A = \frac{1+\sqrt{3}}{4\sqrt{3}}, \qquad B=-\frac{1-\sqrt{3}}{4\sqrt{3}}$$
Hence
$$y_n = \frac{1}{4\sqrt{3}}\left(\alpha^{n+1} -\beta^{n+1}\right) $$
Since $a_n = x_n + y_n + z_n = 2y_{n-1} + 2y_n$, we get 
\begin{align*}
a_n &= \frac{1}{2\sqrt{3}}\left(\alpha^n(1+\alpha) - \beta^n(1+\beta)\right)\\
&= \left(\frac{2+\sqrt{3}}{2\sqrt{3}}\right)\alpha^n - \left(\frac{2-\sqrt{3}}{2\sqrt{3}}\right)\beta^n
\end{align*}
Hence the number of sequences of length $n$ that contain $00$ is 
$$3^n - \left(\frac{2+\sqrt{3}}{2\sqrt{3}}\right)(1+\sqrt{3})^n + \left(\frac{2-\sqrt{3}}{2\sqrt{3}}\right)(1-\sqrt{3})^n$$
