Find the generating function or closed form for the recurrence relation $a_n = a_{n-1} + 4a_{n-2} + 2a_{n-3}$

Question

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 !

Answer 1

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*}

Answer 2

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