Find the generating function or closed form for the recurrence relation $a_n = a_{n-1} + 4a_{n-2} + 2a_{n-3}$ I was trying to solve this recurrence relation using generating function
$a_n = a_{n-1} + 4a_{n-2} + 2a_{n-3} \qquad : \quad a_0 =1,a_1 =1,a_2 =5, $
I did in the following way 
$
\begin{align*} 
&G(x) = \sum_{n=0}^{\infty}a_n.x^n \\
&G(x) = a_0x^0 +a_1x^1+a_2x^2+\sum_{n=3}^{\infty}a_n.x^n \\
&G(x) = 1.x^0 +1.x^1+5.x^2+\sum_{n=3}^{\infty}\left ( a_{n-1} +4.a_{n-2} + 2.a_{n-3} \right ).x^n \\
&G(x) = 1.x^0 +1.x^1+5.x^2+ x.\sum_{n=2}^{\infty}a_nx^n + 4x^2.\sum_{n=1}^{\infty}a_nx^n + 2x^3.\sum_{n=0}^{\infty}a_nx^n\\
&G(x) = 1.x^0 +1.x^1+5.x^2+ x.\left [ G(x) - 1 - x \right ] + 4x^2.\left [ G(x) - 1 \right ] + 2x^3.G(x)\\
&G(x) = \frac{1}{1-x-4x^2-2x^3} \\
\end{align*}$
Now how to get the closed form in terms of $n$ after this?
If any other methods available to find the closed form please mention.
Thanks !

Hint: factorise the denominator and thereby rewrite the fraction as a linear combination of factors of the form $\frac{1}{1-\lambda x}$. And to get you started, one root by inspection is $-1$.
