I have two series that I'm supposed to evaluate using generating functions.

(a) $0+1+2+3+4+ ...+ n$
(b) $0 + 3 + 12+...+3n^2$

I know how to evaluate (a) using walks in Pascal's triangle: the answer is $\frac{n(n+1)}{2}$.

For part (b), I'm not sure how to solve it whatsoever.

For both problems I need to evaluate using generating functions. Can someone explain how I do this?

  • 1
    $\begingroup$ Remember an alternative way to write $1+x+x^2+...+x^n$? Differentiate that and see what you get. $\endgroup$ – TokenToucan Apr 5 '16 at 18:25
  • $\begingroup$ Yeah--I know that the differential of that in its alternative form is $\frac{1}{(1-x)^2}$. But what do I do from there to evaluate the sum? $\endgroup$ – BrianW Apr 5 '16 at 18:28
  • $\begingroup$ That is not quite right, that's from $1+x+x^2+...$ $\endgroup$ – TokenToucan Apr 5 '16 at 18:29
  • $\begingroup$ Should my generating function be $\frac{x}{(1-x)^2}$? I think that gets my coefficient to equal the power of $x$ it's affiliated with. $\endgroup$ – BrianW Apr 5 '16 at 18:47

We can start out with $$\frac 1 {1-x} = 1+x+x^2+...$$

We want to get $1+x+...+x^n$, so we do $$\frac 1 {1-x} - \frac {x^{n+1}} {1-x}$$

Since that knocks out the $x^{n+1}$th term and those past it. Now we differentiate to get

$$1+2x+3x^2+ ... + nx^{n-1} = \frac{nx^{n+1} - (n+1)x^{n} + 1}{(1-x)^2}$$

Evaluate that at 1 and we would get the sum. Unfortunately, that causes problems on the RHS. so we will have to take a limit as $x \rightarrow 1$. Top and bottom go to 0 so we apply L'Hospital:

$$\rightarrow \frac{n(n+1)x^n - n(n+1)x^{n-1}}{2(x-1)} = \frac{n(n+1)}{2}\frac{x^{n-1}(x-1)}{x-1} = \frac{n(n+1)}{2}x^{n-1} \rightarrow \frac {n(n+1)}{2}$$

The second problem is similar (but you should try it on your own first). You will have to multiply by $x$ and take an extra derivative to get the $n^2x^n$ terms, then try to evaluate at $1$ again and multiply by 3 to finish it all up.


If you don't know caluclus...

$\sum_0^n ((i+1)^3 - i^3) = (n+1)^3$ If this is not clear, then write out the first few terms and see that everything cancels except the last term. This is called a telescoping series.

$\sum_0^n (3i^2 + 3i +1) = (n+1)^3\\ \sum_0^n 3i^2 = (n+1)^3-3/2(n+1)(n)-n$

And there is a very nice "picture proof" out there, that I don't have a link to.... after googling for it. Here is a far better answer than I have already provided.

Proving $\sum_{k=1}^n{k^2}=\frac{n(n+1)(2n+1)}{6}$ without induction


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.