Recurrence relation for the number of codewords of length $n$ from {0, 1, 2} with no two $0$’s appearing consecutively I'm supposed to use recurrence relations to find the number of codewords $b_n$ of length $n$ from the alphabet $\{0, 1, 2\}$ such that no two $0$’s appear consecutively.
After reading about this online, I feel that I should do this as follows:
Let $c_n$ be the number of codewords that start with $0$, $d_n$ be the number of codewords that start with $1$, and $e_n$ be the number of codewords that start with $2$ (all with length $n$). Then
$$b_n = c_n + d_n + e_n$$
where $c_n = d_{n-1}+e_{n-1}$, $\ d_n = c_{n-1}+d_{n-1}+e_{n-1}$, and $e_n = c_{n-1}+d_{n-1}+e_{n-1}$ with $c_1=d_1=e_1=1$. 
Is this method correct? I am having quite a bit of trouble with recurrence relations.
 A: Sure, that should work.  Note that $$d_{n}=b_{n-1}=e_n\implies b_n=c_n+2b_{n-1}$$  and $$c_n=b_{n-1}-c_{n-1}$$  But $b_{n-1}=c_{n-1}+2b_{n-2}$ so $$c_n=2b_{n-2}$$  It follows that $$\boxed {b_n=2b_{n-1}+2b_{n-2}}$$
Direct argument:  the good sequences which start with $1$ or $2$ are obtained by prepending $1,2$ in front of any good sequence. That's the $2b_{n-1}$  The good sequences that start with $0$ are obtained by prepending either $01$ or $02$ in front of any good sequence.  That's the $2b_{n-2}$
Sanity check:  the good length $2$ sequences are $01,02,10,11,12,20,21,22$ so $b_2=8$ and the bad length $3$ sequences are $000,100,200,001,002$ so $b_3=27-5=22$ and we check that $$22=b_3=2\times (b_1+b_2)=2\times (3+8)$$ which is true.
As a more thorough sanity check, it is easy to implement your simultaneous recursions and check that they match this one for modest $n$.
A: The simple answer is that given a codeword of length $n-1$ we can add $10$ or $20$ to the end. Given a code word of length $n$ we can add $1$ or $2$ to the end. All code words of length $n+1$ can be gotten this way uniquely. So: $$b_{n+1}=2b_n+2b_{n-1}$$

There is a nice nerdy general approach to this sort of problem. 
Let $u_n$ be the number of codewords of length $n$ than end in $0$ and $v_n$ the number of codewords of length $n$ that do not end in $0$. 
Now, $v_{n+1}=2v_n+2u_n$ - we can add $1,2$ to the end of any sequence of length $n$ And $u_{n+1}=v_n$, because we can add $0$ to any sequence that did not end in $0$.
$$\begin{pmatrix}u_{n+1}\\v_{n+1}\end{pmatrix}=\begin{pmatrix}0&1\\2&2\end{pmatrix}\begin{pmatrix}u_n\\v_n\end{pmatrix}$$
Thus, inductively:
$$\begin{pmatrix}u_{n}\\v_{n}\end{pmatrix}=\begin{pmatrix}0&1\\2&2\end{pmatrix}^n\begin{pmatrix}0\\1\end{pmatrix}
$$
Now, $A=\begin{pmatrix}0&1\\2&2\end{pmatrix}$ has characteristic polynomial $x^2-2x-2$, which means $A^2=2A+2I$, and hence you get:
$$\begin{pmatrix}u_{n+1}\\v_{n+1}\end{pmatrix}=A^{n+1}\begin{pmatrix}0\\1\end{pmatrix}=(2A+2I)A^{n-1}\begin{pmatrix}0\\1\end{pmatrix}=2\begin{pmatrix}u_{n}\\v_{n}\end{pmatrix}+2\begin{pmatrix}u_{n-1}\\v_{n-1}\end{pmatrix}$$
and therefore, since we are looking for $b_n=u_n+v_n=\begin{pmatrix}1&1\end{pmatrix}\begin{pmatrix}u_{n}\\v_{n}\end{pmatrix}$, we get:
$$b_{n+1}=2b_{n}+2b_{n-1}.$$
More generally, if $W_n = BA^nC$ for compatible matrices $B,A,C$, where $A$ is an $m\times m$ matrix, then $W_n$ satisfies:
$$W_{n+m}+a_{m-1}W_{n+m-1}+a_{m-2}W_{n+m-2}+\cdots +a_0W_{n}=0$$
where $x^m+a_{m-1}x^{m-1}+\cdots+a_0$ is the characteristic polynomial of $A$.
For example if you have an alphabet $\Sigma$ with $m$ letters and restrictions on which letters can follow which other letters, you get $A=(a_{ij})$ for $i,j\in \Sigma$ such that $a_{ij}=1$ if $j$ is allowed to follow $i$ and $0$ otherwise. Then:
$$b_n=\begin{pmatrix}1&\cdots&1\end{pmatrix}A^{n-1}\begin{pmatrix}1\\\vdots\\1\end{pmatrix}$$
Therefore, the given the characteristic polynomial for $A$ (or even the minimal polynomial for $A$) you can determine the linear recursion.
In your case $A=\begin{pmatrix}0&1&1\\1&1&1\\1&1&1\end{pmatrix}.$ This $A$ has characteristic polynomial $x^3-2x^2-2x$, but the factor of $x$ is irrelevant because you still get (for $n>0$) that $A^{n+2}=(2A^2+2A)A^{n-1}=(2A+2I)A^{n}$.
