Deriving a recurrence relation for a ternary string

Question

Consider ternary strings (consisting of only numbers $0,1,2$).
For $n\geq 1$, let $a_n$ be the number of ternary strings of length $n$, where there are no consecutive $1$'s or $2$'s.
Find a relation for $a_n$.

This is my attempt:
Call a ternary string "good" if if does not contain consecutive $1$'s or $2$'s.
Case 1: The first digit is a $0$.
So we can then form a good string in $a_{n-1}$ ways.
Case 2: The first two digits start with $10$ or $20$.
Then we can form a good string in $2 \times a_{n-2}$ ways.

Case 3: First two digits are $12$.
We do not want the third digit to be a $2$. So we count the number of ways to form a good string of length $n-2$ less the number of ways to form a string of length $n-3$, given the first three digits are $122$.
This is done in $a_{n-2} - a_{n-3}$ ways.

Case 4: First two digits are $21$. This is similarly done in $a_{n-2}-a_{n-3}$ ways.
So the total is $a_n = a_{n-1} + 4a_{n-2} - 2a_{n-3}$.
However, the solution says that it is
$a_n = 2a_{n-1}+a_{n-2}$.
Why is my answer incorrect?

Answer 1

In case 3, you must subtract the number of good strings of length $n-2$ that start with $2$, but that is not simply $a_{n-3}$, because a good string of length $a_{n-3}$ could start with $2$.

You should count separately the strings that end in $0$, $1$, and $2$. Call the number of such strings $S_0(n)$, $S_1(n)$ and $S_2(n)$, and let $T(n) = S_0(n) + S_1(n) + S_2(n)$ be the total number of strings of length $n$ (this is what you are after).

You can append a $0$ to any string: $$\begin{align} S_0(n) &= T(n-1) \end{align} $$

You can append a $1$ to any string that does not end in $1$, and a $2$ to any string that does not end in $2$:

$$\begin{align} S_1(n) &= S_0(n-1) + S_2(n-1) \\ S_2(n) &= S_0(n-1) + S_1(n-1) \end{align} $$

Because of the symmetry, write $S_{12}(n) = S_1(n) + S_2(n)$ (so that $T(n) = S_0(n) + S_{12}(n)$), and add the last two equations: $$\begin{align} S_{12}(n) &= 2S_0(n-1) + S_{12}(n-1) \end{align} $$

Now, we have: $$\begin{align} T(n) &= S_0(n) + S_{12}(n) \\ &= 3S_0(n-1) + 2S_{12}(n-1) \\ &= S_0(n-1) + 2T(n-1) \\ &= T(n-2) + 2T(n-1) \end{align} $$