## Tuesday, 14 December 2010

### Multiple geometric summation

Recently I found that applications of geometric summation has been a popular topic among senior interschool competitions, the idea to solve them is actually easy, but only a few students are able to tackle them.

1)Recall: geometric summation
We mainly concerns infinite sum, so for all |r|<1, a+ar+ar^2+... = a(1+r+r^2+...) = a/(1-r)
Example: 1+1/2+1/4+... = 2.

2)A special case
We should note that 1/r+1/r^2+1/r^3+... = 1/(r-1).
Example: 1/8+1/64+1/512+... = 1/7.

3)Summation we uses the sigma sign to denote the summation.
e.g. Σ k (from 0 to 3) = 0+1+2+3 = 6
Double summation: Σ(x: from a to b)Σ(y: from c to d) f(x,y) = f(a,c)+f(a,c+1)+...+f(a+d)+f(a+1,c)+...+f(b,d)
Sometimes the inner summation's first and last term is bonded by the outer summation.
e.g. Σ (x: from a to c) Σ (y: from x to 2x) f(x,y) = f(a,a)+f(a,a+1)+...+f(a,2a)+f(a+1,a+1)+...+f(c,2c).

The following geometric summation, unless specified, adds from 1 to infinity.

4)Classic doubles
e.g. Evaluate Σ i / 2^i.
You may find that it's not a strict G.S. but we can solve it by G.S. by spliting terms.
1/2 + 2/4 + 3/8 + 4/16
= (1/2+1/4+1/8+1/16+...)+(1/4+1/8+1/16+...)+(1/8+1/16+...)+...
= (1)(1/2+1/4+1/8+1/16+...)+(1/2)(1/2+1/4+1/8+...)+(1/4)(1/2+1/4+1/8+...)+...
=(1+1/2+1/4+...)(1/2+1/4+1/8+...)
=(1)(2)=2

You may notice that G.S. turn sum to one terms, so double G.S. turns the sum into product of two terms.
When it's in forms of Σi/10^k, the result is k/(k-1)^2, which suits "product of two terms" and the lemma of special case on G.S..

5)Double summation in terms of summation
If we want to tackle double G.S. by summation we will have to use double summation.
e.g. Evaluate Σ i/3^i.
Σ i/3^i
=Σ 1/3^i + 1/3^i +...    (i terms)
=Σ (i:: from 1 to infinity) Σ (j: from 1 to i) 1/3^j
=Σ (i: from 1 to infinity) Σ (j from i to infinity) 1/3^j    (Note: this can be shown on a grpah.)
=Σ 1/(3-1)3^(i-1)
=(1/2) Σ 1/3^(i-1)
=(1/2)(3/(3-1))
=3/4

6)Further applications:
e.g. Evaluate 7/10^2 + 77/10^4 + 777/10^6+...
7/10^2 + 77/10^4 + 777/10^6 +...
=(7/10^2+7/10^4+7/10^6+...) + (70/10^4+70/10^6+...) + (700/10^6+700+10^8+...)+...
=7(1/10^2+1/10^4+...)+7/10(1/10^2+1/10^4+...)+7/100(1/10^2+1/10^4+...)=...
=7(1+1/10+1/100+...)(1/10^2+1/10^4+...)
=7(11/10)(1/99)
=7/90

7)Extension: multiple G.S.
e.g. Evaluate Σi^2 / 2^i.
Does it converge?     Yes since (i^2/2^i)' is eventually negative and tends to 0.
Use this identity: i^2 = 1+3+5+...+(2i-1).
1/2+4/4+9/8+16/16+...
=1/2+1/4+3/4+1/8+3/8+5/8+1/16+3/16+5/16+7/16+...
=(1/2+1/4+1/8+...)+3(1/4+1/8+...)+5(1/8+1/6)+...
=1+3/2+5/4+7/8+9/16+11/25+...
=(1+1/2+1/4+1/8+...)+2(1/2+1/4+1/8+...)+2(1/4+1/8+...)+...
=2+2+1+1/2+1/4+...=6
Note that three times of G.S. is used here.

8)More to explore
-Prove the special case of G.S.
-Evaluate Σ (n^2+n)/7^(n+1).
-Evaluate Σ i^3/3^i  and Σ i^4/4^i.
-Find the rage of y'<0 of the graph y = i^x/x^i, where x is a positive real. Hence or otherwise prove Σ (x : from 2 to fintiniy) Σ i^x/x^i converges.
-Show that (x-1)^xΣ i^x/x^i is an integer in terms of i) "product of n terms" and "calculation analysis"
-Explore more about polylogarithm function and this G.S.

fin.