Tricki
a repository of mathematical know-how

Revision of Partial summation from Tue, 21/04/2009 - 22:55

Quick description

Suppose that you are trying to bound the size of a sum of a product of two functions, one reasonably smooth and the other reasonably oscillating, and suppose that you believe that the oscillations give rise to cancellation that causes the sum to be small. Then a technique similar to integration by parts may well give rise to an efficient way of proving this.

Prerequisites

Basic real analysis. Complex numbers.

Example 1: Abel summation

Let z be a complex number, of modulus 1 but not equal to 1, and let a_0,a_1,a_2,\dots be a sequence of positive real numbers tending to zero. Then the sum \sum_{n=0}^\infty a_nz^n converges.

How might we prove this? Why do we even believe it?

One can give a geometrical answer to the second question. If you plot the points a_0, a_0+a_1z, a_0+a_1z+a_2z^2, a_0+a_1z+a_2z^2+a_3z^3, and so on, drawing straight line segments between them, then you obtain a piecewise linear curve that seems to spiral inwards to a point. (The closer z is to 1, the bigger this "spiral" tends to be.)

How about a rigorous proof? Well, the observation on which the proof is based is that the set of numbers of the form 1+z+z^2+\dots+z^n is bounded. Indeed, the formula for summing a geometric progression tells us that

 1+z+z^2+\dots+z^n=\frac {1-z^{n+1}}{1-z},

which has modulus at most 2/|1-z|.

Since we know how to work out sums of the above form, it makes sense to try to use this information to investigate the sum \sum_{n=0}^\infty a_nz^n, which we do by breaking it up into sums of the form we like. We can set aside the convergence issues for now and just look at the sum \sum_{n=0}^N a_nz^n. In order to split this up into polynomials with constant coefficients, we begin by noting that the sequence (a_0,a_1,a_2,\dots,a_N) can be split up as

(a_0-a_1,0,0,\dots)+(a_1-a_2,a_1-a_2,0,0,\dots)+(a_2-a_3,a_2-a_3,a_2-a_3,0,\dots)+\dots+(a_N,\dots,a_N).

The best motivation for this splitting comes from drawing a picture of the "graph" of the sequence (a_0,a_1,\dots,a_N), which we are chopping up horizontally.

Note iconAttention This article is in need of attention. If anyone knows how to produce a nice picture for this it will really help.

To be continued soon.

General discussion