Summation by parts

In mathematics, summation by parts transforms the summation of products of sequences into other summations, often simplifying the computation or (especially) estimation of certain types of sums. The summation by parts formula is sometimes called Abel's lemma or Abel transformation.

Definition

Suppose $\{f\_k\}$ and $\{g\_k\}$ are two sequences. Then,:$sum\_\{k=m\}^n\; f\_k(g\_\{k+1\}-g\_k)\; =\; left\; [f\_\{n+1\}g\_\{n+1\}\; -\; f\_m\; g\_m\; ight]\; -\; sum\_\{k=m\}^n\; g\_\{k+1\}(f\_\{k+1\}-\; f\_k)$.

Using the forward difference operator $Delta$, it can be stated more succinctly as:$sum\_\{k=m\}^n\; f\_kDelta\; g\_k\; =\; left\; [f\_\{n+1\}\; g\_\{n+1\}\; -\; f\_m\; g\_m\; ight]\; -\; sum\_\{k=m\}^n\; g\_\{k+1\}Delta\; f\_k,$

Note that summation by parts is an analogue to the integration by parts formula,:$int\; f,dg\; =\; f\; g\; -\; int\; g,df.$

Newton series

The formula is sometimes stated in the slightly different form

:$sum\_\{k=0\}^n\; f\_k\; g\_k=\; f\_n\; sum\_\{k=0\}^n\; g\_k\; -\; sum\_\{j=0\}^\{n-1\}\; left(\; f\_\{j+1\}-\; f\_j\; ight)\; sum\_\{k=0\}^j\; g\_k$,

which itself is a special case ($M=1$) of this more general rule

:$sum\_\{k=0\}^n\; f\_k\; g\_k=\; sum\_\{i=0\}^\{M-1\}\; left(\; -1\; ight)^i\; f\_\{n-i\}^\{(i)\}\; G\_\{n-i\}^\{(i+1)\}+\; left(\; -1\; ight)\; ^\{M\}\; sum\_\{j=0\}^\{n-M\}\; f\_j^\{(M)\}\; G\_j^\{(M)\}$,

which results from iterated application of the initial formula. The auxiliary quantities are Newton series:

:$f\_j^\{(M)\}=\; sum\_\{k=0\}^M\; left(-1\; ight)^\{M-k\}\; \{M\; choose\; k\}\; f\_\{j+k\}$

and

:$G\_j^\{(M)\}=\; sum\_\{k=0\}^j\; \{j-k+M-1\; choose\; M-1\}\; g\_k;$here, $\{n\; choose\; k\}$ is the binomial coefficient.

The initial equation may be stated alternatively as:$sum\_\{k=0\}^n\; f\_k\; g\_k\; =\; f\_0\; sum\_\{k=0\}^n\; g\_k+\; sum\_\{j=0\}^\{n-1\}\; (f\_\{j+1\}-f\_j)\; sum\_\{k=j+1\}^n\; g\_k.$

Method

For two given sequences $(a\_n)\; ,$ and $(b\_n)\; ,$, with $n\; in\; N$, one wants to study the sum of the following series:
$S\_N\; =\; sum\_\{n=0\}^N\; a\_n\; b\_n$

If we define $B\_n\; =\; sum\_\{k=0\}^n\; b\_k$ ,
then for every n>0, $b\_n\; =\; B\_n\; -\; B\_\{n-1\}\; ,$

$S\_N\; =\; a\_0\; b\_0\; +\; sum\_\{n=1\}^N\; a\_n\; (B\_n\; -\; B\_\{n-1\})$
$S\_N\; =\; a\_0\; b\_0\; -\; a\_1\; B\_0\; +\; a\_N\; B\_N\; +\; sum\_\{n=1\}^\{N-1\}\; B\_n\; (a\_n\; -\; a\_\{n+1\})$
Finally $S\_N\; =\; a\_N\; B\_N\; -\; sum\_\{n=0\}^\{N-1\}\; B\_n\; (a\_\{n+1\}\; -\; a\_n)$

This process, called an Abel transformation, can be used to prove several criteria of convergence for $S\_N\; ,$ .

imilarity with an integration by parts

The formula for an integration by parts is $int\_a^b\; f(x)\; g\text{'}(x),dx\; =\; left\; [\; f(x)\; g(x)\; ight]\; \_\{a\}^\{b\}\; -\; int\_a^b\; f\text{'}(x)\; g(x),dx$
Beside the boundary conditions, we notice that the first integral contains two multiplied functions, one which is integrated in the final integral ( $g\text{'}\; ,$ becomes $g\; ,$ ) and one which is derivated ( $f\; ,$ becomes $f\text{'}\; ,$ ).

The process of the Abel transformation is similar, since one of the two initial sequences is summed ( $b\_n\; ,$ becomes $B\_n\; ,$ ) and the other one is discretely derivated ( $a\_n\; ,$ becomes $a\_\{n+1\}\; -\; a\_n\; ,$ ).

Applications

Let's consider that $a\_N\; b\_N\; ightarrow\; 0$, otherwise it is obvious that $(S\_N),$ is a divergent series.

If $(B\_n)\; ,$ is bounded by a real M and $sum\_\{n=0\}^N\; (a\_\{n+1\}\; -\; a\_n)$ is absolutely convergent, then $(S\_N),$ is a convergent series.

$|S\_N|\; le\; |a\_N\; b\_N|\; +\; sum\_\{n=0\}^\{N-1\}\; |B\_n|\; |a\_\{n+1\}-a\_n|$

And the sum of the series verifies:$S\; =\; sum\_\{n=0\}^infty\; a\_n\; b\_n\; le\; M\; sum\_\{n=0\}^infty\; |a\_\{n+1\}-a\_n|$

ee also

*Convergent series
*Divergent series
*Integration by parts
*Abel's theorem
*Abel transform

References

*planetmathref|id=3843|title=Abel's lemma