So, I have solved the problem with consecutive zeros and ones and many other combinations, but this one I couldn't.
They left a hint that I could use the complement, but I have no idea where it comes into play here. I assume when I want to calculate the opposite of the instance when $0$ is followed by a $2$, because that's the problematic one.
Denote by $A_n$ the number of admissible strings and by $O_n$ the number of admissible strings ending with $0$. Then $A_n=3A_{n-1}-O_{n-1}$, since you may append any of three digits to an admissible string of length $n-1$, unless this string ends in $0$, in which case you may only append $0$ or $2$. Furthermore $O_{n-1}=A_{n-2}$ since you may append a $0$ to any admissible string. It follows that the recursion you are after is $$A_n-3A_{n-1}+A_{n-2}=0\qquad(n\geq3)\ .$$