# How to solve this recurrence relation using generating functions: $a_n = 10 a_{n-1}-25 a_{n-2} + 5^n\binom{n+2}2$?

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

then?

• $5^n\binom{n+2}2=5^n\dfrac{(n+1)(n+2)}2$ Feb 11, 2019 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.

• Great answer, thank you! Feb 11, 2019 at 10:38
• @GEdgar I would say an algebraic equation for $f(x) =\sum_{n=0}^\infty a_n x^n$. Feb 11, 2019 at 10:38
• The indices can begin at $0.~ a_i=0$ for $i<0$. Feb 11, 2019 at 10:42
• @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$) Feb 11, 2019 at 10:45

$$\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}$$

• This is a working approach. @Robert Z provided a faster one though. In any case, thank you! Feb 11, 2019 at 10:39