Monday 16 January 2012

Generating functions part 2: by integration on log series

Last time we have talked about proving identities through differentiation on known identities, so this time we will deal with identities by integration, mainly on the log series. We know that calculus is the bridge between rational functions and logarithm series. We can transform series of rational expression into geometric sum, then by integration we can express logarithm series in terms of infinite sum of polynomials.

Example. show that $\sum^{n}_{i=1}\frac{1}{i(i+1)}=\frac{n}{n+1}$
Observe that $\int \frac{1}{x+x^2}dx=\ln x-\ln (x+1)+C$
(I don't expect readers to have the ability to compute this one because it involve a very tricky integral $\int \csc x dx$ which is pretty hard.)
Now $\sum [\ln x-\ln (x+1)+C_i]=C-\ln (x+1)$ where C is a constant.
Differentiate both sides ones, $\sum \frac{1}{x(x+1)}=C-\frac{1}{1+x}$, by checking the first term, C=1 so $\sum \frac{1}{x(x+1)}=\frac{n}{n+1}$, Q.E.D..

Example. Show that $\ln (1+x)=\sum \frac{-(-x)^n}{n}$ for $x\in [-1,1]$.

In traditional approach this proof involves limit of exponential series and tricky substitution but with this integration approach we can make it easy.

Since $\frac{1}{1-x}=\sum x^r$ for $x\in [-1,1]$, integration gives $\int \frac{1}{1\pm x}=\ln (1\pm x)+C$, we have $\ln (1-x)+C=\sum \frac{x^{r+1}}{r+1}$ for $x\in [-1,1]$. Now we solve the C and we get zero. Q.E.D..
Note that the original summation starts with the term 1, after integration it starts with the term x.

Before this one ends, we've got a technical analytical problem: how to determine C in the summation term after integration?
Let's say $\sum f(x)=g(x)$. After integration it's like $\sum(F(x)+C(x))=G(x)+C'(x)$. Since $\frac{d(G(x)+C'(x))}{dx}=g(x)$, C'(x) is a constant function. If LHS is a finite sum, i.e., it's in the form $\sum^{n}f(x)=g(n)$, by considering $F(n)=\sum^{n}[F(i)+C(i)]-\sum^{n-1}[F(i)-C(i)]$ we have $\Delta C(n)=0$, so C(n) is a zero function. The constant from integration comes from the first term. If it's infinite sum like the second example, we write $G(x)+C=\sum [F(x)+C'(x)]$, differentiate RHS once should give f(x), so C(x) is a constant function. However since it's an infinite sum. If it's non-zero LHS diverges which trivially a contradiction. Therefore the constant term in the summation is zero as well. How about the constant term on the LHS, must it be zero? It's left for readers to explore themselves.

Exercise:
1a) Show that $\frac{1}{2}\ln \frac{1+x}{1-x}=\sum^{\infty}_{i=1} \frac{(2i-1)^{2i-1}}{2i-1}$.
b) Hence show that $\frac{1}{2}\ln (1+\frac{1}{n})=\sum^{\infty}_{i=1}\frac{1}{(2i-1)(2n+1)^{2i-1}}$
c) By (a) show that the two infintie sums are equal: $\sum \frac{1}{2ix^{2i}},2\sum \frac{1}{(2i-1)(2x^2-1)^{2i-1}}$.
2) If $\phi \neq n\pi$, show that $\ln \csc \phi=\sum^{\infty}_{i=1}\frac{\cos ^{2i}\phi}{2i}$
3) Prove or disprove the existance of non-zero constant term derived from the integration of known identities.
4) In the second example show that C=0.

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