## Sunday, 15 January 2012

### Generating functions part 1: by differentiation on GS

Happy new year and hope all of you success in 2012.

In the summation of geometric series, the method of expanding terms is quite complicated and you might wonder if there's a faster way to do it, we call that the method of generating functions, through differentiation.

We all know that $\sum^{\infty}_{r=1}\frac{1}{2^r}=1$ and $\sum^{n}_{r=1}\frac{1}{2^r}=1-\frac{1}{2^n}$. Now we try to differentiate both side once. However we can directly use a generalized result to be differentiated:

$\sum^{\infty}_{r=0}x^r=\frac{1}{1-x}$ where |x| < 1.
Now differentiate both side once, we can state r as constant just like when we do explicit differentiation or partial differentiation:
$\sum^{\infty}_{r=1}rx^{r-1}=\frac{1}{(1-x)^2}$. Note that the original term for r=0 is eliminated since $\frac{d1}{dx}=0$. The recent term for r=1 is from $\frac{dx}{dx}=1$ the original term r=1.

Therefore we have $\sum^{\infty}_{r=0}rx^{r-1}=\frac{1}{(1-x)^2}$.

(From now on it's infinite sum from r=1.)

Note that $\sum rx^r=\sum rx^{r-1}-\sum x^r$, we have $\sum rx^r = (1-x)^{-2}-(1-x)^{-1}=\frac{x}{(1-x)^2}$.

Check by x = 0.5:
$\sum rx^r=\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+...=\frac{0.5}{(1-0.5)^2}=2$ which is correct.

Now let's differentiate it once again:
$\sum rx^r=\frac{x}{(1-x)^2}$
$\sum r^2x^{r-1}=\frac{x+1}{(1-x)^3}$
Now aware that $\sum r^2x^r=\sum r^2x^{r-1}-\sum (2r+1)x^r=\frac{x+1}{(1-x)^3}-\frac{2x}{(1-x)^2}-\frac{1}{1-x}$
Which gives $\sum r^2x^r=\frac{x(x+1)}{(1-x)^3}$.
As we have discussed before, for x = 0.5, $\sum r^2(0.5)^r=6$
Now check $\frac{0.5(0.5+1)}{(1-0.5)^3}=6$ which is correct as well.

Here's another method to derive the geometric sum:
Consider the expression $\sum (r+1)x^r$ we have two equlity against it:
1) $\sum (r+1)x^r=x^{-1}\sum rx^r -1$
2) $\sum (r+1)x^r=\sum rx^r +\sum x^r -1$
Now comparing both sides:
$(1-x^{-1})\sum rx^r=\frac{1}{1-x}$, $\sum rx^r =\frac{x}{(1-x)^2}$

Similarly, consider $\sum (r+1)^2x^r$,
$x^{-1}\sum r^2x^r -1=\sum r^2x^r +2\sum rx^r+\sum x^r -1$
$(1-x^{-1})\sum r^2x^r=\frac{2x}{(1-x)^2}+\frac{1}{1-x}$
$\sum r^2x^r = \frac{x(x+1)}{(1-x)^3}$ which is the same result as above.

Exercise:
1) Compute the followings: (Typical A-level questions)
$\sum C^{n}_{r}2^r$, $\sum nC^{n}_{r}2^r$, $\sum n^3C^{n}_{r}2^r$, summation from 0 to n.
2) Show that $\sum^{n}_{i=1}\frac{i(C^{n}_{i})^2}{n+1-i}=\frac{n(2n)!}{(n+1)(n!)^2}$ (HKALE Pure 2007 I 1b)
3) Compute the infinite sum $\sum \frac{x^{r}}{r}$ where $x\in [-1,1]$