Hint: One approach is to define four functions. Let $OE(n)$ be the number of words of length $n$ which have an odd number of $1$'s and an even number of $2$'s and three similar ones. Write the recurrence relations between these four. They stay closely balanced, so they are all just about $\frac {3^n}4$ in each one. Maybe you can find a proof of the small correction (note that this is not an integer, which the final result must be)
Added: you are right that $EO(n)=OE(n)$ by symmetry. That is a good thing to think about, as it gets you down to three functions. You need to write a recurrence for each function separately. A word where both are odd can come from a word where both are odd by adding a 3, from EO by adding a 1, or from OE by adding a 2. So $OO(n)=EO(n-1)+OE(n-1)+OO(n-1)$ Your starting condition is $EE(0)=1, \text{others}(0)=0$ because the empty word is even in both. I made a spreadsheet to calculate the first dozen values or so. You can then see a pattern in the corrections, which you can prove from the recurrences. Your final answer is then $EO(n)$
This can be done recursively. We have $a_1 = 3$ and $a_2 = 7$ by inspection.
Then for $n>2$, we see that there are three possible ways to start a sequence: $AB$, $B$, or $C$. Depending on which one we choose, we recurse into a smaller sequence of known size, where the counting process is repeated all over again.
This suggests the recurrence $a_n = 2a_{n-1} + a_{n-2}$ with $a_1 = 3$ and $a_2 = 7$.
To get a closed form, note that the characteristic polynomial is $x^2 - 2x - 1 = 0$, or $(x-1)^2-2 = 0$, which has roots $1 + \sqrt{2}$ and $1 - \sqrt{2}$. Therefore:
$a_n = A(1 + \sqrt{2})^n+B(1 - \sqrt{2})^n$ for some unknown $A,B$.
But we already know $a_1$ and $a_2$:
$3 = A(1 + \sqrt{2})^1+B(1 - \sqrt{2})^1$
$7 = A(1 + \sqrt{2})^2+B(1 - \sqrt{2})^2$
Solving this system yields $A = \frac{1}{2}+\frac{1}{\sqrt{2}}, B = \frac{1}{2}-\frac{1}{\sqrt{2}}$. Therefore:
$$a_n = (\frac{1}{2}+\frac{1}{\sqrt{2}})(1 + \sqrt{2})^n+(\frac{1}{2}-\frac{1}{\sqrt{2}})(1 - \sqrt{2})^n$$
Simplifying:
$$a_n = \frac{1}{2} ((1+\sqrt{2})^{n+1}+(1-\sqrt{2})^{n+1})$$
Best Answer
$\color{blue}{\text{Case I-)}}$ It start up with $0$:
This is obvious , as you wrote , it is $a_{n-1}$
$\color{blue}{\text{Case II-)}}$
For each $k$ between zero and $(n-2)$ , there could be string of $(n-k-1)$ alternating $1's$ and $2's$ which followed by a zero , so followed by no pair of consecutive ones or twos.Then there are $2a_{n-(n-k)}=2a_k$ such strings.For example:
$20.... \rightarrow a_{n-2}$
$10.... \rightarrow a_{n-2}$
$120.... \rightarrow a_{n-3}$
$210.... \rightarrow a_{n-3}$
$121212.... \rightarrow a_{0}$
$212121.... \rightarrow a_{0}$
So , $$2a_{n-2}+2a_{n-3}+....+2a_{0}$$
$\color{blue}{\text{Case III-)}}$
Ternary strings that always alternate bewtween $1$ and $2$ , we have two such strings such that
$121212....$
$212121...$
So we have two such strings.
Now , lets sum these three cases to reach $a_n$ such that $$a_n=(a_{n-1})+(2a_{n-2}+2a_{n-3}+....+2a_{0})+2$$
However , we cannot find any value using this long recursion ,so lets make a manipulation such that $$a_{n-1}=(a_{n-2})+(2a_{n-3}+2a_{n-4}+....+2a_{0})+2$$
Now , lets subtract them such that
$$a_n=(a_{n-1})+(2a_{n-2}+2a_{n-3}+....+2a_{0})+2$$
$$a_{n-1}=(a_{n-2})+(2a_{n-3}+2a_{n-4}+....+2a_{0})+2$$
$$a_n-a_{n-1}=a_{n-1}+a_{n-2}$$
So , $$a_n=2a_{n-1}+a_{n-2}$$