How can we solve the following recurrence relation using GF?

$a_n = 10 a_{n-1}-25 a_{n-2} + 5^n {n+2 \choose 2}$ , for each $n>2, a_0 = 1, a_1 = 15$

I think that most of it is pretty straightforward. What really concerns me is this part

$5^n{n+2 \choose 2}$

Problem further analyzed

After trying to create generating functions in the equation we end up in this

$\sum_{n=2}^\infty a_n x^n = 10 \sum_{n=2}^\infty {a_{n-1}} \sum_{n=2}^\infty a_{n-2} x^n + \sum_{n=2}^\infty {n+2 \choose 2}5^nx^n$

Lets take this part:

$ \sum_{n=2}^\infty {n+2 \choose 2}5^nx^n = \sum_{n=2}^\infty \frac{(n+1)(n+2)}{2} 5^nx^n $


  • $\begingroup$ $5^n\binom{n+2}2=5^n\dfrac{(n+1)(n+2)}2$ $\endgroup$ – Shubham Johri Feb 11 at 10:13
  • $\begingroup$ It is multiplied. Edited the question so that it is clearer. $\endgroup$ – Dimitris Prasakis Feb 11 at 10:13

Hint for finding the GF.

Note that $(n+1)(n+2)x^n=\frac{d^2}{dx^2}\left(x^{n+2}\right)$ and therefore $$\sum_{n=2}^\infty {n+2 \choose 2}5^nx^n = \frac{1}{2\cdot 5^2}\frac{d^2}{dx^2}\left( \sum_{n=2}^\infty (5x)^{n+2} \right).$$ Then recall that $\sum_{n=0}^{\infty}z^n=\frac{1}{1-z}$.

Moreover in your attempt it should be $$\sum_{n=2}^\infty a_n x^n = 10 \sum_{n=2}^\infty {a_{n-1}}x^n-25 \sum_{n=2}^\infty a_{n-2} x^n + \sum_{n=2}^\infty {n+2 \choose 2}5^nx^n.$$ that is $$\sum_{n=2}^\infty a_n x^n = 10x \sum_{n=1}^\infty {a_{n}}x^n-25x^2 \sum_{n=0}^\infty a_{n} x^n + \sum_{n=2}^\infty {n+2 \choose 2}5^nx^n.$$ Can you take it from here and find $f(x) =\sum_{n=0}^\infty a_n x^n$?

Alternative way for finding $a_n$ without the GF.

The given recurrence is a non-homogeneous linear recurrence relation with constant coefficients with characteristic equation $$z^2-10z+25=(z-5)^2=0$$ and non-homogeneous term $5^n {n+2 \choose 2}$ which is a second degree polynomial multiplied by a power of $5$, which is the root of multiplicity $2$ of the characteristic equation. Hence the general term of the recurrence with $a_0 = 1$, $a_1 = 15$ has the form $$a_n= 5^n(An^4+Bn^3+Cn+D)$$ where $A,B,C,D$ are real constant to be determined.

  • $\begingroup$ Great answer, thank you! $\endgroup$ – Dimitris Prasakis Feb 11 at 10:38
  • $\begingroup$ @GEdgar I would say an algebraic equation for $f(x) =\sum_{n=0}^\infty a_n x^n$. $\endgroup$ – Robert Z Feb 11 at 10:38
  • $\begingroup$ The indices can begin at $0.~ a_i=0$ for $i<0$. $\endgroup$ – Shubham Johri Feb 11 at 10:42
  • $\begingroup$ @ShubhamJohri the description of the problem says foreach $n \geq 2$ given that $a_0 = 1, a_1 = 15$. Thus the indices start at 2 and then we got to degrade them to $0$, so that we use the definition of generating functions (where indices start from $0$) $\endgroup$ – Dimitris Prasakis Feb 11 at 10:45
  • 1
    $\begingroup$ @DimitrisPrasakis I edited my answer with an alternative method. $\endgroup$ – Robert Z Feb 11 at 11:02

$\sum_{n=0}^\infty {n+2 \choose 2}5^nx^n = \frac12\sum_{n=0}^\infty(n^2+3n+2)(5x)^n=\frac12[\sum_{n=0}^\infty n^2y^n+3\sum_{n=0}^\infty ny^n+2\sum_{n=0}^\infty y^n]$

where $y=5x$. You will need the following series sums:

$(1)\sum_{n=0}^\infty n^2y^n=\dfrac{y(1+y)}{(1-y)^3}\\(2)\sum_{n=0}^\infty ny^n=\dfrac y{(y-1)^2}$

  • $\begingroup$ This is a working approach. @Robert Z provided a faster one though. In any case, thank you! $\endgroup$ – Dimitris Prasakis Feb 11 at 10:39

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.