# 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?

• for the general case of q-ary words refer to this other post Apr 3, 2017 at 18:10
• The recurrence relation is in oeis.org/A186244 . Feb 13 at 13:40
• Thank you @R.J.Mathar. I was coincidentally thinking about my Discrete Math professor from the class I took 10 years ago recently. He made some witty comment about making sure we submit the homework assignments online before midnight a day before it was due in case the whole internet becomes unavailable due to the protests against SOPA and PIPA Feb 14 at 0:06

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

• fixed the typos Apr 4, 2012 at 2:21
• @Pat: And I’ve removed the parenthetical note. Apr 4, 2012 at 2:26
• thank you very much for confirming my conjecture Apr 4, 2012 at 2:36
• @BrianM.Scott what if string end with $12$ ,$21$,$22$,$11$ ? Oct 3, 2016 at 7:48
• @sourav: Those possibilities are all covered by the second sentence of the answer. Oct 3, 2016 at 9:14

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.

• The third term must have a $+$ sign. Apr 4, 2018 at 12:07
• @Muralidharan: you are right, now fixed, thanks. Apr 4, 2018 at 12:09

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