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?
On
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
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.