Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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 $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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