3
$\begingroup$

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 !

$\endgroup$
  • 1
    $\begingroup$ Use \cdot for the multipliers. $\endgroup$ – J.G. Mar 19 '17 at 8:23
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +1 thanks ! for a detail answer! I was looking for the second variation and you did both ways. $\endgroup$ – Debashish Mar 19 '17 at 16:12
  • $\begingroup$ @Debashish: You're welcome! Good to see the answer is useful. :-) $\endgroup$ – Markus Scheuer Mar 19 '17 at 16:13
  • $\begingroup$ Can u explain how you got the next step of equation $(2)$ from $(2)$ ? $\endgroup$ – Taxicab Sep 20 '18 at 18:48
  • $\begingroup$ @UnknownMathMan: The comment section addressing (2) and (3) is not clear? $\endgroup$ – Markus Scheuer Sep 20 '18 at 18:55
  • 2
    $\begingroup$ @UnknownMathMan: The coefficient $[x^{n-j}]$ in (2) has non-negative exponent $n-j$. To assure the non-negativity of $[x^{n-j-k}]$ in (3), the index $k$ in the inner sum has the minimum of $j$ and $n-j$ as upper limit. $\endgroup$ – Markus Scheuer Sep 20 '18 at 19:09
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.