6
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ $5^n\binom{n+2}2=5^n\dfrac{(n+1)(n+2)}2$ $\endgroup$ Feb 11, 2019 at 10:13

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Great answer, thank you! $\endgroup$ Feb 11, 2019 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, 2019 at 10:38
  • $\begingroup$ The indices can begin at $0.~ a_i=0$ for $i<0$. $\endgroup$ Feb 11, 2019 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$ Feb 11, 2019 at 10:45
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This is a working approach. @Robert Z provided a faster one though. In any case, thank you! $\endgroup$ Feb 11, 2019 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.