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