# Finding the coefficient in the closed form of the generating function

I try to solve the recursion $a_n=5a_{n-1}+5^n$ with $a_0=1$ with generating function, but I could not find the coefficient of $x^n$ in the closed form \begin{eqnarray*} g(x)&=&a_0+\sum^n_1a_nx^n\\ g(x)&=&1+\sum^n_1(5a_{n-1}+5^n)x^n\\ g(x)&=&1+5\sum^n_1a_{n-1}x^n + \sum^n_15^nx^n\\ g(x)&=&1+5x\sum^n_0a_{n-1}x^{n-1} + \sum^n_1(5x)^n\\ g(x)&=&1+5xg(x)+\frac{1}{1-5x}-1\\ g(x)(1-5x)&=&\frac{1}{1-5x}\\ g(x)&=&\frac{1}{(1-5x)^2} \end{eqnarray*} I tried the partial fraction and wish to find something in the form $\frac{A}{1-5x}+\frac{B}{1-5x}$, but it did not work out because the method of partial fraction required this in form of $\frac{A}{1-5x}+\frac{B}{(1-5x)^2}$, so it seems like partial fraction does not help. Can someone help.

-

(I haven't checked your algebra, but it's plausible. Check you get the right answer at the end by working out a few terms.)

The ingredient you're missing is a series expansion of $(1+u)^{-2}$, which is given by a binomial series, http://en.m.wikipedia.org/wiki/Binomial_series

You get $$\sum_0^\infty x^n \frac{(-2)(-3)(-4)(-5)\cdots (-n-1)}{(1)(2)(3)(4)\cdots (n)}$$

and you can simplify the fraction a lot! This should be enough of hint.

-
I know if it is in the form $\frac{1}{(1-x)^2}$, then I can use binomial series to get $\frac{1}{(1-x)^2}=\binom{n+2-1}{n}$, but the $5$ gives me trouble. – user62453 Apr 21 '13 at 0:48
The 5 is the easy part! Let $u=5x$, expand this, then substitute back in. You will get $5^n$ multiplying what you had before (up to minus signs that we're being careless about.) – Sharkos Apr 21 '13 at 7:35
is it true that $[x^n]$ in $\frac{1}{(1-\alpha x)^m}=(\alpha)^n\cdot\binom{n+m-1}{n}$? – user62453 Apr 21 '13 at 15:00
The $\alpha$ part is right, yes! $f(\alpha x) =f(u)=\sum a_n u^n = \sum a_n (\alpha x)^n$ – Sharkos Apr 21 '13 at 15:03
thank you for helping! – user62453 Apr 21 '13 at 15:04

You get the generating function: $$g(z) = \frac{1}{(1 - 5 z)^2} = \sum_{n \ge 0} \binom{-2}{n} (-1)^n 5^n z^n = \sum_{n \ge 0} \binom{n + 2 - 1}{2 - 1} 5^n z^n = \sum_{n \ge 0} (n + 1) \cdot 5^n z^n$$ so that: $$a_n = (n + 1) \cdot 5^n$$

-