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

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