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