proof with recurrence relation How can we proof that number ternary strings that do not contain two consecutive 0s or 1s is 
$a_n = 2a_{n-1} + a_{n-2}$
What I tried so far:
Let $a_n$ be the number ternary strings that do not contain two consecutive 0s or 1s. If the first digit start with 2 there will be $a_{n-1}$ such strings. Or if the first digit start with 0 there will be $ (2/3) a_{n-1}$ such strings. Same goes for the case starting with 1. That means $(4/3)a_{n-1}$ and in total $(4/3)a_{n-1} + a_{n-1} = (7/3) a_{n-1}$
And if the first digit is 0 and second 1 or 2 there'll be $a_{n-2}$
Similarly starting with 1 and second digits are 0 or 2 there'll be $a_{n-2}$
and  in total $ 2a_n{-2}$
So as you can see I get $a_n =(7/3)a_{n-1} + 2a_{n-2}$
I have no clue what I am missing here
 A: Your problem is that you are assuming that the number of such strings of length $n-1$ starting with $0$, $1$, and $2$ are all equal (and so getting your figures of $\frac{2}{3}a_{n-1}$ by removing the ones which start with a $0$, for instance). This is not in fact the case, as you can see by looking at the strings of length $2$: there are three such strings that start with a $2$, and only two such strings each starting with a $0$ or a $1$.
Instead:  consider any such string of length $n-1$.  We can make a string of length $n$ by appending either of the two digits which are not the same as the one at the end of the string to the end (e.g., if the string ends in $0$, you can append $1$ or $2$).  There are $2a_{n-1}$ ways to do this.  On the other hand, to any such string of length $n-2$ we can append "22".  I'll leave it to you to convince yourself that these are in fact the only possibilities, so that $a_n = 2a_{n-1} + a_{n-2}$.
A: let $a_n^j$ for $n \in \mathbb{N}$ and $j \in S=\{0,1,2\}$ denote the number of strings of length $n$ which contain neither of the substrings $00$ and $11$, and with the $n^{th}$ symbol $j$ and define $$a_n = \sum_{k \in S} a_n^k$$
we have $\forall j \in S $ 
$$a_0^j = 0\\
a_1^j = 1$$ 
and $\forall n \gt 1 $ we have
$$ a_n^2 = a_{n-1}\\
a_n^1 = a_{n-1}^0 +a_{n-1}^2\\
a_n^0 = a_{n-1}^1 +a_{n-1}^2\\
$$
adding the three equations together gives
$$
a_n = a_{n-1}+(a_{n-1}^0+a_{n-1}^1 +a_{n-1}^2)+a_{n-1}^2 \\
= 2a_{n-1}+a_{n-2}
$$
