Recursion for the number of words of length $n$ over the alphabet $\{0, 1, 2\}$ such that there are neither $11$ nor $22$ blocks Let $a_n$ be the length of words over an alphabet $\{0,1,2\}$ such that there are neither $11$ nor $22$ "blocks".
I. e. $001020$ would be allowed, $001120$ wouldn't because we have a $11$ block.
I have to show that $$a_n=2a_{n-1}+a_{n-2}$$
It looks like this recursion dissects the question into three cases (and adds them all up):

*

*The word of length $n$ ending with $0$: We have: $\underbrace{\cdots \cdots \cdots }_{a_{n-1}}0$

*The word of length $n$ ending with $1$: We have $\cdots \cdots \cdots 1$. Now we'll have to be careful though, since the digit that preceeds $1$ can't be $1$. It has to be a $0$ or a $2$. Do I have to distinguish these cases as well? Say, it is $0$, then $\underbrace{\cdots \cdots \cdots}_{a_{n-2}} 01$. Likewise if it was $2$. How do I take into account this ambiguity?

*The word of length $n$ ending with $2$ is essentially the same as the one ending with $1$.

It would make sense to me if it'd be $a_n=a_{n-1}+2\cdot a_{n-2}$.
 A: $\color{blue}{\text{Case I-)}}$ It start up with $0$:

*

*$0...\rightarrow a_{n-1}$
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}$$
A: It is always fine if the last two digits are different.  We always have two choices for the next digit.  That gives $2a_{n-1}$.  But we can also end with $00$.  That gives $a_{n-2}$.
A: Define $b_n$ to be the number of acceptable sequences ending in $0$, $c_n$ the number ending in $1$, and $d_n$ be the number ending in $2$, so we have $a_n = b_n+c_n+d_n$.  A $0$ can follow any digit, a $1$ can only follow a $0$ or $2$, and a $2$ can only follow a $0$ or $1$, so
$$\begin{align}
b_n &= b_{n-1} + c_{n-1} + d_{n-1}  \tag{1} \\
c_n &= b_{n-1} + d_{n-1} \tag{2} \\
d_n &= b_{n-1} + c_{n-1} \tag{3}
\end{align}$$
Adding $(1)$, $(2)$ and $(3)$,
$$\begin{align}
b_n+c_n+d_n &= 3b_{n-1} + 2c_{n-1} + 2d_{n-1} \\
a_n &= 2a_{n-1} + b_{n-1} \\
\end{align}$$
Applying $(1)$ with $n$ replaced by $n-1$,
$$\begin{align}
a_n &= 2a_{n-1} + b_{n-2} + c_{n-2} + d_{n-2} \\
&= 2a_{n-1} + a_{n-2}
\end{align}$$
