Solving combinatorical problem using characteristic polynomial 
How many $6$ length strings above $\left\{1,2,3,4\right\}$ are there such that $24$ and $42$ aren't allowed.  

The suitable recurrence relation for this problem is: $a_{n+2} = 2a_{n-1} + 4a{n-2}$. Hence, the characteristic polynomial is: $x^2 -2x -4 = 0$.It's roots are: $1+\sqrt5,1-\sqrt5$.  
So, the genral function is: $\alpha (1+\sqrt5)^n + \beta (1-\sqrt5)^n$ 
We know that: $a_0=1$ and $a_1=4$. Hence, 
$\beta = \frac{1}{2} - \frac{3}{2\sqrt5}$,
$\alpha = \frac{1}{2} + \frac{3}{2\sqrt5}$
All in all,
$$(\frac{1}{2} + \frac{3}{2\sqrt5})(1+\sqrt5)^n + (\frac{1}{2} - \frac{3}{2\sqrt5})(1-\sqrt5)^n$$
Now, for $n=6$ the result is $1344$, but the book says $1216$.  
Who's right?
 A: Let $a_n$ be the number of strings of length n,
$b_n$ be the number of strings of length n starting with 1 or 3,
$c_n$ be the number of strings of length n starting with 2, and
$d_n$ be the number of strings of length n starting with 4.
Then $a_n=b_n+c_n+d_n$, $b_n=2a_{n-1}$, $c_n=b_{n-1}+c_{n-1}$, and $d_n=b_{n-1}+d_{n-1}$.  
Substituting the last 3 equations into the first equation gives
$a_n=2a_{n-1}+2b_{n-1}+c_{n-1}+d_{n-1}=2a_{n-1}+b_{n-1}+(b_{n-1}+c_{n-1}+d_{n-1})=2a_{n-1}+2a_{n-2}+a_{n-1}$, 
so $a_n=3a_{n-1}+2a_{n-2}$.
Starting with $a_0=1$ and $a_1=4$, we can substitute into this recurrence relation to get
$a_2=14$, $a_3=50$, $a_4=178$, $a_5=634$, and $a_6=2258$.
A: We may solve such kind of problems using directed graph/finite automaton. 
Consider the following graph:
\begin{align*}
  A = \left[\begin{array}{rrrrrrr}
& \mathrm{I} & \mathrm{O} & \mathrm{2} & \mathrm{4} & \mathrm{24} & \mathrm{42}\\
\mathrm{I} & 0 & 2 & 1 & 1 & 0 & 0 \\
\mathrm{O} & 0 & 2 & 1 & 1 & 0 & 0 \\
\mathrm{2} & 0 & 2 & 1 & 0 & 1 & 0 \\
\mathrm{4} & 0 & 2 & 0 & 1 & 0 & 1 \\
\mathrm{24} & 0 & 0 & 0 & 0 & 0 & 0 \\
\mathrm{42} & 0 & 0 & 0 & 0 & 0 & 0
\end{array}\right]
\end{align*}
We can now obtain the generating functions for all entries by computing:
$$\left(I-x\, A\right)^{-1}$$
and the g.f. we require is the sum of first four columns in the first row of the inverted matrix, which turns out to be:
\begin{align*}
  G(x) &= \dfrac{1+x}{1-2\, x-3\, x^2} \\
  &= \dfrac{1}{4}\left(\dfrac{1+\dfrac{1}{\sqrt{17}}}{\dfrac{\sqrt{17}-3}{4}-x}-\dfrac{1-\dfrac{1}{\sqrt{17}}}{\dfrac{\sqrt{17}+3}{4}+x}\right)
\end{align*}
Extracting $[x^n]$ from the above gives us:
\begin{align*}
  a_n &= \dfrac{1}{4}\left(\dfrac{1+\dfrac{1}{\sqrt{17}}}{\left(\dfrac{\sqrt{17}-3}{4}\right)^{n+1}}-(-1)^n\, \dfrac{1-\dfrac{1}{\sqrt{17}}}{\left(\dfrac{\sqrt{17}+3}{4}\right)^{n+1}}\right) \\
  &\sim  \dfrac{1}{4}\, \dfrac{1+\dfrac{1}{\sqrt{17}}}{\left(\dfrac{\sqrt{17}-3}{4}\right)^{n+1}}
\end{align*}
and the required answer is $a_6 = 2258$
