Summation by parts

From Wikipedia, the free encyclopedia
Jump to: navigation, search
"Abel transformation" redirects here. For another transformation, see Abel transform.

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.

Statement[edit]

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\right] - \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_k\Delta g_k = \left[f_{n+1} g_{n+1} - f_m g_m\right] - \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.

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.

Newton series[edit]

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

\begin{align}
\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{align}

which represent a special cases (M=1) of the more general rule

\begin{align}\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^{(M)}_{j} 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{align}

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

f_j^{(M)}:= \sum_{k=0}^M \left(-1 \right)^{M-k} {M \choose k} f_{j+k}

and

G_j^{(M)}:= \sum_{k=j}^n {k-j+M-1 \choose M-1} g_k,
\tilde{G}_j^{(M)}:= \sum_{k=0}^j {j-k+M-1 \choose M-1} g_k.

A remarkable, particular (M=n+1) result is the noteworthy identity

\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, {n \choose k} is the binomial coefficient.

Method[edit]

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} \,  and

S_N = a_0 b_0 + \sum_{n=1}^N a_n (B_n - B_{n-1}),
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  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 \, .

Similarity with an integration by parts[edit]

The formula for an integration by parts is \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 ( g' \, becomes g \, ) and one which is differentiated ( f \, becomes f' \, ).

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 differenced ( a_n \, becomes a_{n+1} - a_n \, ).

Applications[edit]

The Cauchy criterion gives

\begin{align}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{align}

where a is the limit of a_n. As \sum b_n is convergent, B_N is bounded independently of N, say by B. As a_n-a go to zero, so go the first two terms. The third term goes to zero by the Cauchy criterion for \sum b_n. The remaining sum is bounded by

\sum_{n=N}^{M-1} |B_n| |a_{n+1}-a_n| \le B \sum_{n=N}^{M-1} |a_{n+1}-a_n| = B|a_N - a_M|

by the monotonicity of a_n, and also goes to zero as N \to \infty.

  • Using the same proof as above, one shows that
  1. if the partial sums B_N form a bounded sequence independently of N ;
  2. if \sum_{n=0}^\infty |a_{n+1} - a_n| < \infty (so that the sum \sum_{n=N}^{M-1} |a_{n+1}-a_n| goes to zero as N goes to infinity) ; and
  3. if \lim a_n = 0

then S_N = \sum_{n=0}^N a_n b_n is a convergent series.

In both cases, the sum of the series satisfies:  |S| = \left|\sum_{n=0}^\infty a_n b_n \right| \le B \sum_{n=0}^\infty |a_{n+1}-a_n|

See also[edit]

References[edit]