Summation by parts

src: 1.bp.blogspot.com

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.

Video Summation by parts

Statement

Suppose ${\displaystyle \{f_{k}\}}$ and ${\displaystyle \{g_{k}\}}$ are two sequences. Then,

${\displaystyle \sum _{k=m}^{n}f_{k}(g_{k+1}-g_{k})=\left[f_{n}g_{n+1}-f_{m}g_{m}\right]-\sum _{k=m+1}^{n}g_{k}(f_{k}-f_{k-1}).}$

Using the forward difference operator ${\displaystyle \Delta }$, it can be stated more succinctly as

${\displaystyle \sum _{k=m}^{n}f_{k}\Delta g_{k}=\left[f_{n}g_{n+1}-f_{m}g_{m}\right]-\sum _{k=m}^{n-1}g_{k+1}\Delta f_{k},}$

Note that summation by parts is an analogue to the integration by parts formula,

${\displaystyle \int f\,dg=fg-\int g\,df.}$

An alternative statement is

${\displaystyle f_{n}g_{n}-f_{m}g_{m}=\sum _{k=m}^{n-1}f_{k}\Delta g_{k}+\sum _{k=m}^{n-1}g_{k}\Delta f_{k}+\sum _{k=m}^{n-1}\Delta f_{k}\Delta g_{k}}$

which is analogous to the integration by parts formula for semimartingales.

Note also that although applications almost always deal with convergence of sequences, the statement is purely algebraic and will work in any field. It will also work when one sequence is in a vector space, and the other is in the relevant field of scalars.

Maps Summation by parts

Newton series

The formula is sometimes given in one of these - slightly different - forms

${\displaystyle {\begin{aligned}\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}\\&=f_{n}\sum _{k=0}^{n}g_{k}-\sum _{j=0}^{n-1}\left(f_{j+1}-f_{j}\right)\sum _{k=0}^{j}g_{k},\end{aligned}}}$

which represent a special case (${\displaystyle M=1}$) of the more general rule

${\displaystyle {\begin{aligned}\sum _{k=0}^{n}f_{k}g_{k}&=\sum _{i=0}^{M-1}f_{0}^{(i)}G_{i}^{(i+1)}+\sum _{j=0}^{n-M}f_{j}^{(M)}G_{j+M}^{(M)}=\\&=\sum _{i=0}^{M-1}\left(-1\right)^{i}f_{n-i}^{(i)}{\tilde {G}}_{n-i}^{(i+1)}+\left(-1\right)^{M}\sum _{j=0}^{n-M}f_{j}^{(M)}{\tilde {G}}_{j}^{(M)};\end{aligned}}}$

both result from iterated application of the initial formula. The auxiliary quantities are Newton series:

${\displaystyle f_{j}^{(M)}:=\sum _{k=0}^{M}\left(-1\right)^{M-k}{M \choose k}f_{j+k}}$

and

${\displaystyle G_{j}^{(M)}:=\sum _{k=j}^{n}{k-j+M-1 \choose M-1}g_{k},}$

${\displaystyle {\tilde {G}}_{j}^{(M)}:=\sum _{k=0}^{j}{j-k+M-1 \choose M-1}g_{k}.}$

A remarkable, particular (${\displaystyle M=n+1}$) result is the noteworthy identity

${\displaystyle \sum _{k=0}^{n}f_{k}g_{k}=\sum _{i=0}^{n}f_{0}^{(i)}G_{i}^{(i+1)}=\sum _{i=0}^{n}(-1)^{i}f_{n-i}^{(i)}{\tilde {G}}_{n-i}^{(i+1)}.}$

Here, ${\displaystyle {n \choose k}}$ is the binomial coefficient.

src: humanphysiology.academy

Method

For two given sequences ${\displaystyle (a_{n})}$ and ${\displaystyle (b_{n})}$, with ${\displaystyle n\in \mathbb {N} }$, one wants to study the sum of the following series:
${\displaystyle S_{N}=\sum _{n=0}^{N}a_{n}b_{n}}$

If we define ${\displaystyle B_{n}=\sum _{k=0}^{n}b_{k},}$  then for every ${\displaystyle n>0,}$  ${\displaystyle b_{n}=B_{n}-B_{n-1}}$  and

${\displaystyle S_{N}=a_{0}b_{0}+\sum _{n=1}^{N}a_{n}(B_{n}-B_{n-1}),}$

${\displaystyle S_{N}=a_{0}b_{0}-a_{0}B_{0}+a_{N}B_{N}+\sum _{n=0}^{N-1}B_{n}(a_{n}-a_{n+1}).}$

Finally  ${\displaystyle 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 ${\displaystyle S_{N}}$ .

src: i.ytimg.com

Similarity with an integration by parts

The formula for an integration by parts is ${\displaystyle \int _{a}^{b}f(x)g'(x)\,dx=\left[f(x)g(x)\right]_{a}^{b}-\int _{a}^{b}f'(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 ( ${\displaystyle g'}$ becomes ${\displaystyle g}$ ) and one which is differentiated ( ${\displaystyle f}$ becomes ${\displaystyle f'}$ ).

The process of the Abel transformation is similar, since one of the two initial sequences is summed ( ${\displaystyle b_{n}}$ becomes ${\displaystyle B_{n}}$ ) and the other one is differenced ( ${\displaystyle a_{n}}$ becomes ${\displaystyle a_{n+1}-a_{n}}$ ).

src: rsif.royalsocietypublishing.org

Applications

• It is used to prove Kronecker's lemma, which in turn, is used to prove a version of the strong law of large numbers under variance constraints.
• Summation by parts is frequently used to prove Abel's theorem.
• If ${\displaystyle \sum b_{n}}$ is a convergent series, and ${\displaystyle a_{n}}$ a bounded monotone sequence, then ${\displaystyle S_{N}=\sum _{n=0}^{N}a_{n}b_{n}}$ remains a convergent series.

The Cauchy criterion gives

${\displaystyle {\begin{aligned}S_{M}-S_{N}&=a_{M}B_{M}-a_{N}B_{N}+\sum _{n=N}^{M-1}B_{n}(a_{n+1}-a_{n})\\&=(a_{M}-a)B_{M}-(a_{N}-a)B_{N}+a(B_{M}-B_{N})+\sum _{n=N}^{M-1}B_{n}(a_{n+1}-a_{n}),\end{aligned}}}$

where a is the limit of ${\displaystyle a_{n}}$. As ${\displaystyle \sum b_{n}}$ is convergent, ${\displaystyle B_{N}}$ is bounded independently of ${\displaystyle N}$, say by ${\displaystyle B}$. As ${\displaystyle a_{n}-a}$ go to zero, so go the first two terms. The third term goes to zero by the Cauchy criterion for ${\displaystyle \sum b_{n}}$. The remaining sum is bounded by

${\displaystyle \sum _{n=N}^{M-1}|B_{n}||a_{n+1}-a_{n}|\leq B\sum _{n=N}^{M-1}|a_{n+1}-a_{n}|=B|a_{N}-a_{M}|}$

by the monotonicity of ${\displaystyle a_{n}}$, and also goes to zero as ${\displaystyle N\to \infty }$.

• Using the same proof as above, one shows that

1. if the partial sums ${\displaystyle B_{N}}$ form a bounded sequence independently of ${\displaystyle N}$ ;
2. if ${\displaystyle \sum _{n=0}^{\infty }|a_{n+1}-a_{n}|<\infty }$ (so that the sum ${\displaystyle \sum _{n=N}^{M-1}|a_{n+1}-a_{n}|}$ goes to zero as ${\displaystyle N}$ goes to infinity) ; and
3. if ${\displaystyle \lim a_{n}=0}$

then ${\displaystyle S_{N}=\sum _{n=0}^{N}a_{n}b_{n}}$ is a convergent series.

In both cases, the sum of the series satisfies: ${\displaystyle |S|=\left|\sum _{n=0}^{\infty }a_{n}b_{n}\right|\leq B\sum _{n=0}^{\infty }|a_{n+1}-a_{n}|}$

src: images.slideplayer.com

See also

• Convergent series
• Divergent series
• Integration by parts
• Cesàro summation
• Abel's theorem
• Abel sum formula

src: www.doteco.com

References

• "Abel's lemma". PlanetMath. 

Source of article : Wikipedia