# Recurrence relation with generating function question

I have to solve the recurrence relation: $$a_n=a_{n-1}+n\quad(n\geq1), \quad a_0=0$$ with generating function. The final result I think should be: $$a_n=\frac {n(n+1)}2$$, but I don't know how to get it from the function. I tried with partial fraction decomposition, but the problem is that I don't know how to deal with denominator. This is what I did: $$\sum_{n=1}^{+\infty}a_nx^n=\sum_{n=1}^{+\infty}a_{n-1}x^n+\sum_{n=1}^{+\infty}nx^n$$$$f(x)-a_0=xf(x)+\frac x{(1-x)^2}$$$$f(x)-xf(x)=\frac x{(1-x)^2}$$$$f(x)(1-x)=\frac x{(1-x)^2}$$$$f(x)=\frac x{(1-x)^3}$$So I have the generating function but I don't know how to get to the result from here.

• Better if you write out what you did & see if we can get you over your difficulty. – Gerry Myerson Jun 11 at 11:04
• Hint: Try applying the Binomial Theorem to $(1-x)^{-3}$ – awkward Jun 11 at 12:11
• Edited with the steps I did – Diego Di Marzo Jun 11 at 12:34

Hint:

By the generalized binomial theorem,

$$(1-x)^{-3}=1+3x+\frac{3\cdot4}{2}x^2+\frac{3\cdot4\cdot5}{3!}+\frac{3\cdot4\cdot5\cdot6}{4!}+\cdots\frac{(n+2)!}{2\,n!}x^n\cdots$$

Also by Taylor $$\frac x{(1-x)^3}=\frac{1-(1-x)}{(1-x)^3}=\frac1{(1-x)^3}-\frac1{(1-x)^2} \\=1+3x+3\cdot4\frac{x^2}2+3\cdot4\cdot5\frac{x^3}{3!}+\cdots-1-2x-2\cdot3\frac{x^2}2-2\cdot3\cdot4\frac{x^3}{3!}+\cdots$$

• I never heard about Binomial Theorem, is this the only way? – Diego Di Marzo Jun 11 at 12:37
• @DiegoDiMarzo: it is the Generalized Binomial Theorem. – Yves Daoust Jun 11 at 12:41
• Got it, can I ask you if this is the only way to have the result? Because I never used it with this kind of problem. – Diego Di Marzo Jun 11 at 12:47
• @DiegoDiMarzo: most probably not. – Yves Daoust Jun 11 at 12:49
• There's always another way to do things, but this is the standard way that everyone teaches and is in all the textbooks. – Gerry Myerson Jun 11 at 12:57