The number of series over $\{0,1,2\}$ without repeating numbers

Question

What is the number of series over $\{0,1,2\}$ with length $n$ without repeating the same number one after the other ($22$ is not allowed but $101$ is), that does not begin and end with the number $2$.
The series $10210$ is good. The series $2002$ is not good because there are two consecutive $0$, and it starts and ends with $2$.
I tried recurrence with the following formula:
$a_n=2a_{n-2}+a_{n-1}$
The reason is that the element before the last has $2$ options according to its previous element. But when I thought about the last element I thought that it can be 1 or 0 according the the element before that.
But if $2$ is the element before last I think the formula is not right.
Should I split it to cases (another formula $b_n$)?

Answer 1

Consider the problem but with the condition that the first and last number is always a $2$. This corresponds to the original problem by chopping of the $2$s:

$$2\underbrace{010120}_{\text{original}}2$$

Let $a_n$ be the number of such sequences of length $n$. Then $a_3 = 2$ is the first nonzero entry.

Now disregarding that the second last number may not be a $2$, it is manifest that each position $2 \ldots n-1$ has $2$ options, accounting for $2^{n-2}$ possibilities.

But observe that those sequences with a $2$ at position $n-1$ correspond bijectively to those constituting $a_{n-1}$:

$$\underbrace{21021212}_{\text{in $a_{n-1}$}}2$$

Thus we obtain the recurrence:

$$a_n = 2^{n-2} - a_{n-1}$$

which is readily solved using standard techniques.