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

Question

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

Answer 1

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

Answer 2

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