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?

Solution 1:

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}\;.$$

Solution 2:

You may also get an explicit formula directly, by invoking Markov chains / deterministic finite automata.
This is the DFA which accepts the strings over $\Sigma=\{0,1,2\}$ with at least two consecutive $0$s:

Its transition matrix is given by $$ P = \begin{pmatrix}2& 1 & 0 \\ 2 & 0 & 1 \\ 0 & 0 & 3 \end{pmatrix} $$ and the characteristic polynomial of this matrix is $(x-3)(x^2-2x-2)$. It follows that the number of strings over $\Sigma$ having length $n$ and containing at least two consecutive $0$s is $$ L_n = A\cdot 3^n + B\cdot (1+\sqrt{3})^n + C \cdot (1-\sqrt{3})^n $$ for some constants $A,B,C$ which can be found by interpolation. Since $L_1=0, L_2=1$ and $L_3=5$ $$\boxed{L_n=3^n-\left(\tfrac{1}{\sqrt{3}}+\tfrac{1}{2}\right)(1+\sqrt{3})^n+\left(\tfrac{1}{\sqrt{3}}-\tfrac{1}{2}\right)(1-\sqrt{3})^n\;}$$ which clearly fulfills the recurrence relation mentioned by Brian Scott.

Solution 3:

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$$