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?
Answer
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.
No comments:
Post a Comment