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 !
 A: Here   are two variants to derive $a_n$. The first one gives a closed form, the other one an explicit expression, which results in a nice binomial identity.

First variant: Partial fractions
In case it's easy to derive the zeros of the denominator of 
  \begin{align*}
G(x) = \frac{1}{1-x-4x^2-2x^3}
\end{align*}
  the partial fraction decomposition is a convenient method. As @J.G. indicated is $x=-1$ a zero.
Omitting some intermediary calculations we obtain
\begin{align*}
G(x)&=\frac{1}{1-x-4x^2-2x^3}\\
&=\frac{1}{1+x}-\frac{2x}{2x^2+2x-1}\\
&=\frac{1}{1+x}-\frac{x}{(x+\frac{1}{2}(1+\sqrt{3}))(x+\frac{1}{2}(1-\sqrt{3}))}\\
&=\frac{1}{1+x}-\frac{1}{2\sqrt{3}}\cdot\frac{1+\sqrt{3}}{\left(x+\frac{1}{2}+\frac{\sqrt{3}}{2}\right)}
+\frac{1}{2\sqrt{3}}\cdot\frac{1-\sqrt{3}}{\left(x+\frac{1}{2}-\frac{\sqrt{3}}{2}\right)}\\
&=\frac{1}{1+x}-\frac{1}{\sqrt{3}}\cdot\frac{1}{1-(1-\sqrt{3})x}+\frac{1}{\sqrt{3}}\cdot\frac{1}{1-(1+\sqrt{3})x}\\
&=\sum_{n=0}^\infty\left[(-1)^n-\frac{1}{\sqrt{3}}(1-\sqrt{3})^n+\frac{1}{\sqrt{3}}(1+\sqrt{3})^n\right]x^n\tag{1}
\end{align*}
Second variant: Geometric series
We can also directly apply a geometric series  expansion. It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a series and obtain
\begin{align*}
[x^n]G(x)&=[x^n]\frac{1}{1-x-4x^2-2x^3}\\
&=[x^n]\sum_{j=0}^\infty  x^j(1+4x+2x^2)^j\\
&=\sum_{j=0}^n[x^{n-j}]\sum_{k=0}^j\binom{j}{k}(2x)^k(2+x)^k\tag{2}\\
&=\sum_{j=0}^n\sum_{k=0}^{\min\{j,n-j\}}\binom{j}{k}2^k[x^{n-j-k}](2+x)^k\\
&=\sum_{j=0}^n\sum_{k=0}^{\min\{j,n-j\}}\binom{j}{k}\binom{k}{n-j-k}2^{3k-n+j}\tag{3}
\end{align*}

Comment:


*

*In (2) we use the linearity of the coefficient of operator and apply the rule
\begin{align*}
[x^{p-q}]A(x)=[x^p]x^qA(x)
\end{align*}
We also set the upper limit of the outer sum to $n$ since the exponent of $x^{n-j}$ is non-negative.

*In (3) we select the coefficient of $x^{n-j-k}$.

Binomial identity:  We derive from (1) and (3) the following binomial identity by changing the order of summation in the outer sum of (3), i.e. $j\rightarrow n-j$.
  \begin{align*}
\sum_{j=0}^n&\sum_{k=0}^{\min\{j,n-j\}}\binom{n-j}{k}\binom{k}{j-k}2^{3k-j}\\
&=(-1)^n-\frac{1}{\sqrt{3}}(1-\sqrt{3})^n+\frac{1}{\sqrt{3}}(1+\sqrt{3})^n\qquad\qquad n\geq 0
\end{align*}

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