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?

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$.
