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.

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


By the generalized binomial theorem,


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

  • 1
    $\begingroup$ I never heard about Binomial Theorem, is this the only way? $\endgroup$ – Diego Di Marzo Jun 11 at 12:37
  • $\begingroup$ @DiegoDiMarzo: it is the Generalized Binomial Theorem. $\endgroup$ – Yves Daoust Jun 11 at 12:41
  • $\begingroup$ 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. $\endgroup$ – Diego Di Marzo Jun 11 at 12:47
  • $\begingroup$ @DiegoDiMarzo: most probably not. $\endgroup$ – Yves Daoust Jun 11 at 12:49
  • 1
    $\begingroup$ There's always another way to do things, but this is the standard way that everyone teaches and is in all the textbooks. $\endgroup$ – Gerry Myerson Jun 11 at 12:57

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.