# Recurrence relation for the number of $n$-digit ternary sequences with no consecutive $1$s or $2$s

Find the recurrence relation for the number of $n$-digit ternary sequences with no consecutive $1$'s or $2$'s.

The solution is $$a_n = a_{n-1} + 2a_{n-2} + 2a_{n-3} + 2a_{n-4} + \dots. \tag1$$

I've thought about this for quite some time and I can't really understand it. I feel like I'm making up my reasoning to fit the solution; rather than understanding why it really is in the above form.

Can someone please explain this combinatorially?

-

As is common in problems of this type, it is useful to define other related sequences. Call a sequence with no two consecutive $1$'s or $2$'s good.

Let $p_n$ be the number of good sequences of length $n$ that end in $0$, $q_n$ the number that end in $1$, and $r_n$ the number that end in $2$.

We have the obvious recurrence $p_{n}=p_{n-1}+q_{n-1}+r_{n-1} =a_{n-1}$.

Also, $q_{n}=p_{n-1} +r_{n-1}$, and $r_{n}=p_{n-1}+q_{n-1}$. This is because, for example, to make a good sequence of length $n$ that ends in $1$, we take a good sequence of length $n-1$ that doesn't end in $1$, and append a $1$.

Add up. We get $a_{n}=2a_{n-1}+p_{n-1}$. But $p_{n-1}=a_{n-2}$. So we end up with the recurrence $$a_{n}=2a_{n-1}+a_{n-2}.$$ From this nice recurrence we can get a closed form. We can also get the recurrence of the post.

For assume by way of induction hypothesis that for a certain number $k$, we have $$a_k=a_{k-1}+2a_{k-2}+2a_{k-3}+\cdots$$ Then $$a_{k+1}=2a_k +a_{k-1}=a_k+(a_{k-1}+a_k)=a_k+(2a_{k-1}+2a_{k-2}+2a_{k-3}+\cdots).$$

-
When you did the induction hypothesis, did you obtain that from the solution or did you deduce that from the closed form? (Very helpful solution, ow!) – AlanH Mar 26 '13 at 8:38
Not from the closed form in terms of $(1\pm \sqrt{2})^n$, but from the short recurrence. – André Nicolas Mar 26 '13 at 10:35

Take a good $n$-digit sequence, i.e., one with no $11$ or $22$ subsequence.

• If it ends in $0$, the initial $(n-1)$-subsequence is good, so there are $a_{n-1}$ good $n$-sequences ending in $0$.

• If it ends in $1$, it must actually end in either $01$ or $21$, and if it ends in $2$, it must actually end in either $02$ or $12$. A $0$ can follow any good sequence, so each good $(n-2)$-sequence gives rise to two good $n$-sequences, one ending in $1$ and one ending in $2$, by appending $01$ or $02$, respectively. Since there are $a_{n-2}$ good $(n-2)$-sequences, that accounts for the $2a_{n-2}$ good $n$-sequences ending in $01$ or $02$. That still leaves the $n$-sequences ending in $21$ or $12$ to be counted.

• If the $n$-sequence ends in $21$, it must actually end in $021$ or $121$; similarly, if it ends in $12$, it must actually end in $012$ or $212$. The $021$ and $012$ cases can now be handled as before: a $0$ can follow any good sequence, so there are $a_{n-3}$ good $n$-sequences ending in $021$ and another $a_{n-3}$ ending in $012$; between them they account for another $2a_{n-3}$ good $n$-sequences, but the $n$-sequences ending in $121$ and $212$ remain to be accounted for.

The pattern should now be pretty clear. In fact we can do better. Suppose that the last $0$ in a given $n$-sequence is in the $k$-th position, where $k<n$. It can follow any of the $a_{k-1}$ good $(k-1)$-sequences, and it must be followed by either $1212\dots$ or $2121\dots$. Thus, for each $k<n$ there are $2a_{k-1}$ good $n$-sequences having their last $0$ in the $k$-th position.

-

Call the number of sequences that interest you that end in 0 $a_n$, if they end in 1 $b_n$, $c_n$ if they end in 2, and $d_n$ for ending in 3. Then clearly: $$a_0 = b_0 = c_0 = d_0 = 1$$ Now think how a sequence that ends in 0 can be built: Add a 0 to any of the others, so $a_{n + 1} = a_n + b_n + c_n + d_n$. To make a sequence ending in 1, anything except a sequence ending in 1 can come before, so it is $b_{n + 1} = a_n + c_n + d_n$. Continuing the same way: \begin{align*} a_{n + 1} &= a_n + b_n + c_n + d_n \\ b_{n + 1} &= a_n + c_n + d_n \\ c_{n + 1} &= a_n + b_n + d_n \\ d_{n + 1} &= a_n + b_n + c_n + d_n \end{align*} This setup serves for any restrictions you care to set up.

Now define generating functions: \begin{align*} A(z) &= \sum_{n \ge 0} a_n z^n \\ B(z) &= \sum_{n \ge 0} b_n z^n \\ C(z) &= \sum_{n \ge 0} c_n z^n \\ D(z) &= \sum_{n \ge 0} d_n z^n \end{align*} This gives the system of equations: \begin{align*} \frac{A(z) - 1}{z} &= A(z) + B(z) + C(z) + D(z) \\ \frac{B(z) - 1}{z} &= A(z) + C(z) + D(z) \\ \frac{C(z) - 1}{z} &= A(z) + B(z) + D(z) \\ \frac{D(z) - 1}{z} &= A(z) + B(z) + C(z) + D(z) \end{align*} By sheer luck, the values we are interested in are just the $a_{n + 1}$. Solving the system of equations we get: $$A(z) = \frac{1 + z}{1 - 3 z - 2 z^2}$$ This can be split into (very ugly) partial fractions, and expand the resulting geometric series: $$a_n = - \frac{\sqrt{17} - 1}{\sqrt{17} (\sqrt{17} + 3)} \cdot \left( - \frac{4}{\sqrt{17} + 3} \right)^n + \frac{\sqrt{17} + 1}{\sqrt{17} (\sqrt{17} - 3)} \cdot \left(\frac{4}{\sqrt{17} - 3} \right)^n$$ (this would need some more cleanup, sorry for the mess).

-
Ternary strings are made from $\{0,1,2\}$, why we need to add the term: $d_n$ – Ricardo Cervantes Nov 8 '14 at 3:22