Recursion relation: Number of series length n made of $(0,1,2)$ so that each pair sum is between 1 and 3. [including them]. Recursion relation: Number of series length n made of $(0,1,2)$ so that each pair sum is between 1 and 3. [including them].
So what i did was:


*

*Let $a_n$ be the total number of series length n so that each pair has the correct sum.

*Let $b_n$ be total number of series starting with $0$.

*Let $c_n$ be total number of series starting with $1$.

*Let $d_n$ be total number of series starting with $2$.


Notice that $a_n=b_n+c_n+d_n$.
Recursion relation of $b_n=c_{n-1}+d_{n-1}$ -This makes sure there are no $0,0$.
Recursion relation of $c_n=a_{n-1}$ - Doesn't matter which digit is next.
Recursion relation of $d_n=b_{n-1}+c_{n-1}$ -This makes sure there are no $2,2$.
First off, Did i look at the question right? If so, I'm pretty much stuck on simplifying those recursion relation.
 A: You have set up the recurrence nicely.  I would ignore $a_n$ for now and rewrite $c_n=b_{n-1}+c_{n-1}+d_{n-1}$ to avoid the relation between the $_n$ terms.  You could also use the symmetry that tells you $b_n=d_n$ to get to two recurrences instead of three.  You also need some initial conditions.  Now note that if you have a column vector $\begin {bmatrix} b_n\\c_n\\d_n \end {bmatrix}$ it satisfies the recursion $$\begin {bmatrix} b_n\\c_n\\d_n \end {bmatrix}=\begin {bmatrix} 0&1&1\\1&1&1\\1&1&0 \end {bmatrix}\begin {bmatrix} b_{n-1}\\c_{n-1}\\d_{n-1} \end {bmatrix}$$  As the matrix is symmeteric, it will have a complete set of eigenvalues.  Find them and the corresponding eigenvectors, then the linear combination that represents your initial conditions.
A: Yes, this is a reasonable way to start, though you really want $b_n,c_n$, and $d_n$ to count the number of strings ending in $0,1$, or $2$, respectively, not starting with those digits. Your three recurrences are correct:
$$\begin{align*}
b_n&=c_{n-1}+d_{n-1}\\
c_n&=a_{n-1}\\
d_n&=b_{n-1}+c_{n-1}\;.
\end{align*}\tag{1}$$
Notice that if you subtract the third from the first, you get $$b_n-d_n=d_{n-1}-b_{n-1}=-(b_{n-1}-d_{n-1})\;.\tag{2}$$ You can easily check that $b_1=d_1=1$, so $b_1-d_1=0$, and an easy proof by induction using $(2)$ shows that $b_n=d_n=0$ for all $n\ge 1$, i.e., that $b_n=d_n$. (This is intuitively very reasonable: if you start with a good sequence and change all of the $0$’s to $2$’s and vice versa, you get a good sequence. Thus, the number ending in $0$ and the number ending in $2$ should be the same.)
Now we can simplify $(1)$:
$$\begin{align*}
b_n&=c_{n-1}+b_{n-1}=a_{n-2}+b_{n-1}\\
c_n&=a_{n-1}\;.
\end{align*}\tag{1}$$
Moreover, 
$$\begin{align*}
a_n&=2b_n+c_n\\
&=2b_n+a_{n-1}\\
&=2(a_{n-2}+b_{n-1})+a_{n-1}\\
&=2a_{n-2}+2b_{n-1}+a_{n-1}\\
&=a_{n-2}+(a_{n-2}+2b_{n-1})+a_{n-1}\\
&=a_{n-2}+(c_{n-1}+2b_{n-1})+a_{n-1}\\
&=a_{n-2}+a_{n-1}+a_{n-1}\\
&=a_{n-2}+2a_{n-1}\;.
\end{align*}$$
Let’s check by using the other approach. If I start with a good $(n-1)$-sequence, there are always two digits that I can safely add. (Why?) That accounts for $2a_{n-1}$ good $n$-sequences. If the $(n-1)$-sequence ends in $1$, I can add any of the three digits, so I need to know how many of the good $(n-1)$-sequences end in $1$. Each of those can be obtained by adding a $1$ to a good $(n-2)$-sequence, so there are $a_{n-2}$ of them, and we again get the recurrence $a_n=2a_{n-1}+a_{n-2}$.
In this problem I really think that the second approach is easier unless you’re familiar with matrix methods or generating functions.
A: Define generating functions $A(z) = \sum_{n \ge 0} a_{n + 2} z^n$ and so on (need at least length 2). Write your system as:
$$
\begin{align*}
b_{n + 1} &= c_n + d_n \\
c_{n + 1} &= b_n + c_n + d_n \\
d_{n + 1} &= b_n + c_n
\end{align*}
$$
Then $b_2 = c_2 = d_2 =2$, and:
$$
\begin{align*}
\frac{B(z) - b_2}{z} &= C(z) + D(z) \\
\frac{C(z) - c_2}{z} &= B(z) + C(z) + D(z) \\
\frac{D(z) - d_2}{z} &= B(z) + C(z)
\end{align*}
$$
And also:
$$
A(z) = B(z) + C(z) + D(z)
$$
Solve the linear system for $B(z)$, $C(z)$, $D(z)$, plug into $A(z)$. Split $A(s)$ into partial fractions (possibly with complex roots!), and expand each term by the binomial theorem:
$$
(1 - u)^{-m} = \sum_{n \ge 0} \binom{k + m - 1}{m - 1} u^n
$$
Profit!
