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

Question

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

Answer 1

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

Answer 2

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

Answer 3

There's a nice combinatorial interpretation of these ternary words in terms of integer compositions with parts from the set $\{1, 1', 2\}$, i.e., made from 2s and two kinds of 1s. Such compositions are counted by the Pell numbers. Consider the subset of these where the last part cannot be $1'$. The count for these is your sequence, beginning $1, 3, 7, 17, 41$ with OEIS references A001333 and A078057. First, I show the recurrence for these compositions. Then I discuss connecting them to ternary sequences.

Let $X_n$ be the set of these compositions of $n$, and $x_n = |X_n|$. Clearly $X_1 = \{(1)\}$ and $X_2 = \{(1,1),(1',1),(2)\}$. For $n \ge 3$, we establish the bijection $X_n \cong 2X_{n-1} \cup X_{n-2}$ where $2X_{n-1}$ denotes two copies of $X_{n-1}$. For one copy of $X_{n-1}$, add a $1$ as the new first part, keeping the subsequent parts. For the other copy of $X_{n-1}$, add a $1'$ as the new first part. For the compositions of $X_{n-2}$, add a $2$ as the new first part. These clearly give distinct compositions of $n$ which, because the last part has not been altered, do not end in $1'$. The reverse map from $X_{n}$ is clear: remove the first part.

The nicest connection to ternary words forbids $\{00, 02\}$ instead of $\{00,11\}$, which gives the same count. MacMahon pointed out that a composition of $n$ is determined by a length $n-1$ binary sequence, which can be interpreted as making a cut ($1$) or join ($0$) decision as you as go left-to-right along a length $n$ board. With two kinds of $1$s, we have two kinds of cuts; e.g., $X_2 = \{(1,1),(1',1),(2)\}$ corresponds to $\{1, 2, 0\}$, respectively. For $X_3$, the ternary sequences are all pairs except $00$ which would indicate a part 3 and $02$ which would correspond to $(2,1')$ (the sequence $01$ corresponding to $(2,1)$ is fine). The recursion works analogously: precede one set of the $X_{n-1}$ ternary words by $1$, precede another set by $2$, and precede the $X_{n-2}$ ternary words by $01$.