Number of sequences of $0$s, $1$s, and $2$s with length $n$ such that there is a $0$ somewhere between every pair of $2$s Let $a(n)$ be the number of sequences with length $n$ which consists the digits $0,1,2$ such that between every two occurrences of $2$ there is an occurrence of $0$ (not necessarily next to the $2$'s). An example for good sequence is $0102102$. An example for bad sequence is $01212$.

A. Find a recursion formula for $a(n)$
B. Find an explicit expression for $a(n)$.

My try:
let $x(n)$ be the number of sequences with length $n$ that if we add $2$ at the end of sequence it is still a good sequence with length $n+1$.
Now, if the last digit in the sequence was $0$, then we have to look on the number of good sequences with length $n-1$, hence $\displaystyle a(n-1)$.
If the last digit was $1$, then we now need to look on $x(n-1)$ and work with the same manipulation. This way we get the recursion $x(n)=a(n-1)+x(n-1)$. By induction I can get a recursion formula for $x(n)$, but I don't know how to find a formula for $a(n)$ or find an explicit expression for $a(n)$.
Any help will be appreciated, thank you!

Consider the following:
\begin{align*}
r(n) &:= \text{number of sequences of 0s and 1s} = 2^n \\
s(n) &:= \text{number of sequences of 0s and 1s with at least one $0$} = 2^n - 1 \\
\end{align*}
The corresponding (ordinary) generating functions are
\begin{align*}
R(x) &= \sum_{n \ge 0} 2^n x^n = \frac{1}{1 - 2x} \\
S(x) &= \sum_{n \ge 0} (2^n - 1) x^n = \frac{1}{1 - 2x} - \frac{1}{1 - x}
= \frac{x}{(1-2x)(1-x)}.
\end{align*}
The generating function $A(x)$ of $a(n)$ satisfies, by casework on the number $k$ of $2$s in the sequence:
\begin{align*}
A(x)
&= \underbrace{R(x)}_{k=0} + \underbrace{R(x) x R(x)}_{k=1} + \sum_{k \ge 2} R(x) (x S(x))^{k-1} x R(x) \\
&= R(x) + \sum_{k \ge 1} R(x)^2 S(x)^{k-1} x^{k}  \\
&= R(x) + \frac{x R(x)^2}{1 - x S(x)} \\
&= \frac{1}{1 - 2x} + \frac{x / (1 - 2x)^2}{1 - \frac{x^2}{(1-x)(1-2x)}} \\
&= \frac{1}{1 - 2x} + \frac{x(1-x)}{(1-2x) \left[ (1-2x)(1-x) - x^2 \right]} \\
&= \frac{1 - 3x + x^2}{(1 - 2x)(1 - 3x + x^2)} + \frac{x - x^2}{(1-2x)(1 - 3x + x^2)} \\
&= \frac{1 - 2x}{(1 - 2x)(1 - 3x + x^2)} \\
&= \boxed{\frac{1}{1 - 3x + x^2}}.
\end{align*}

Now that we have the generating function, we realize that $a(n)$ satisfies a much simpler recurrence:
$$
a(n) = 3 a(n-1) - a(n-2)
$$
which follows directly from $A(x) (1 - 3x + x^2) = 1$.
This recurrence can be explained combinatorially as well, and if we had bothered
to be a bit more clever we might have found the recurrence in the first place and saved some algebra.
Conclude either from the recurrence or from searching the first few values in oeis
that in fact
$$
a(n) = f(2n+2)
$$
where $f(k)$ is the $k$th Fibonacci number.
