# Combinatorial explanation to following recurrence relation $a_n = 2 a_{n-1} + a_{n-2}$

Question was the following:

$a_n$ is the number of ternary strings (strings of 0,1,2) which contain no consecutive zeros and no consecutive ones. Find a formula for $a_n$?

By brute force, I found a recurrence relation for $a_n$ as the following:

$a_n = 2 a_{n-1} + a_{n-2}$

Now I am wondering if there is a good combinatorial explanation/proof to my recurrence relation. Can you see something?

Best Regards

-
Terminological note: those are ternary strings, not turning strings. –  Brian M. Scott Apr 8 '13 at 20:00
@BrianM.Scott thank you for correction –  Xentius Apr 8 '13 at 20:02

Let $b_{i,n}$ be the number of strings of length $n$ starting with $i\in\{0,1,2\}$. Then by your rules $$a_n = b_{0,n} + b_{1,n} + b_{2,n} = (b_{1,n-1} + b_{2,n-1}) + (b_{0,n-1} + b_{2,n-1}) + a_{n-1} = 2a_{n-1} + a_{n-2}.$$

ADDITION: This transformation can be translated into a proof by bijection. Let $X_n$ be the set of all sequences of length $n$. We define a map $$(X_{n-1} \times \{A,B\}) \cup X_{n-2} \quad\to\quad X_{n}$$ by ("$\cdot$" denotes concatenation; $\mu$ a sequence in $X_{n-2}$ and $\lambda$ a sequence in $X_{n-1}$):

$(\lambda,A) \mapsto 2\cdot\lambda$

$(\lambda,B)\mapsto\begin{cases} 1\cdot \lambda & \text{if }\lambda\text{ starts with }0\text{ or }2\\ 0\cdot \lambda & \text{if }\lambda\text{ starts with }1 \end{cases}$

$\mu \mapsto 0\cdot 2\cdot \mu$

This is a bijection, essentially because $(\lambda,A)$ gives all strings in $X_n$ starting with $2$, $(\lambda,B)$ gives all strings in $X_n$ starting with $10$, $01$ or $12$, and $\mu$ gives all strings starting with $02$. So $$\left|(X_{n-1} \times \{A,B\}) \cup X_{n-2}\right| = \left|X_n\right|,$$ which is $$2a_{n-1} + a_{n-2} = a_n.$$

-
I guess what @Xentius meant by a combinatorial proof is not this. He seems to be looking for an answer like in this question he asked: math.stackexchange.com/questions/340905/… –  Amadeus Bachmann Apr 8 '13 at 19:42
@AmadeusBachmann exactly! –  Xentius Apr 8 '13 at 19:45
@AmadeusBachmann: I think that azimut's equality has pure (and nice!) combinatorial sense. –  xen Apr 8 '13 at 19:55
I'm a bit baffled why my argumentation shouldn't be combinatorial. @Xentius could you please specify what kind of proof you are looking for? –  azimut Apr 8 '13 at 20:02
@xen I did not say azimut's proof is not combinatorial. I just wanted to say it may not be what Xentius looking for according to his previous questions. But of course only one to confirm this is Xentius. –  Amadeus Bachmann Apr 8 '13 at 20:06

Call a ternary string with no consecutive zeroes and no consecutive ones a good string. For $k=0,1,2$ let $a_n^k$ be the number of good strings of length $n$ ending in $k$. Then it’s clear that

\begin{align*} &a_n^0=a_{n-1}^1+a_{n-1}^2\\ &a_n^1=a_{n-1}^0+a_{n-1}^2\\ &a_n^2=a_{n-1}^0+a_{n-1}^1+a_{n-1}^2=a_{n-1}\;. \end{align*}\tag{1}

And now we can make the following computation:

\begin{align*} a_n&=a_n^0+a_n^1+a_n^2\\ &=a_n^0+a_n^1+a_{n-1}\\ &=a_{n-1}^1+a_{n-1}^0+2a_{n-1}^2+a_{n-1}\\ &=(a_{n-1}^0+a_{n-1}^1+a_{n-1}^2)+a_{n-1}^2+a_{n-1}\\ &=a_{n-1}+a_{n-1}^2+a_{n-1}\\ &=2a_{n-1}+a_{n-1}^2\\ &=2a_{n-1}+a_{n-2} \end{align*}

by the third line of $(1)$.

In more purely combinatorial terms the term $a_{n-1}$ in $a_n=a_n^0+a_n^1+a_{n-1}$ comes from the fact that each good string of length $n$ ending in $2$ is obtained by appending a $2$ to one of the $a_{n-1}$ good strings of length $n-1$. The rest is a little more complicated. If a good string of length $n-1$ ends in $0$ or $2$, I can append a $1$ to it to get a good string of length $n$ ending in $1$; that covers all good strings of length $n$ ending in $01$ or $21$, which is all good strings of length $n$ ending in $1$. Similarly, if a good string of length $n-1$ ends in $1$ or $2$, I can append a $0$ to get a good string of length $n$ ending in $0$, and that accounts for all good strings of length $n$ ending in $0$. Thus, to get the good strings of length $n$ ending in $0$ or $1$ I’ve used each good string of length $n-1$ ending in $0$ once, each good string of length $n-1$ ending in $1$ once, and each good string of length $n-1$ ending in $2$ twice. In other words, I’ve used each good string of length $n-1$ at least once, and I’ve used those ending in $2$ twice. Ignoring for a moment the double use of those ending in $2$, that accounts for another $a_{n-1}$ strings of length $n$. Finally, we already know that each good string of length $n-1$ ending in $2$ is just the extension by a $2$ of a good string of length $n-2$, so the double use of good strings of length $n-1$ ending in $2$ gives us another $a_{n-2}$ good strings of length $n$. Put the pieces together, and we see that $a_n=2a_{n-1}+a_{n-2}$.

-