Summation by parts

Template:Short description Template:Redirect

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. It is also called Abel's lemma or Abel transformation, named after Niels Henrik Abel who introduced it in 1826.<ref>Template:Cite journal</ref>

Statement

Suppose <math>\{f_k\}</math> and <math>\{g_k\}</math> are two sequences. Then,

<math>\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}).</math>

Using the forward difference operator <math>\Delta</math>, it can be stated more succinctly as

<math>\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,</math>

Or, equivalently, using backward difference operator <math>\nabla</math>:

<math>\sum_{k=m}^n f_k\nabla g_k = \left(f_n g_n - f_{m-1} g_{m-1}\right) - \sum_{k=m}^{n} g_{k-1}\nabla f_k,</math>

Both can be used to obtain a more symmetric version:

<math>\sum_{k=m}^n \left(f_k \Delta g_k + g_k \nabla f_k\right) = f_n g_{n+1} - f_{m-1} g_m </math>

Summation by parts is an analogue to integration by parts:

or to Abel's summation formula:

<math>\sum_{k=m+1}^n f(k)(g_{k}-g_{k-1})= \left(f(n)g_{n} - f(m) g_m\right) - \int_{m}^n g_{\lfloor t \rfloor} f'(t) dt.</math>

An alternative statement is

<math>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</math>

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

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

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

<math>\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}</math>

which represent a special case (<math>M = 1</math>) of the more general rule

<math>\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}</math>

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

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

and

<math>G_j^{(M)}:= \sum_{k=j}^n {k-j+M-1 \choose M-1} g_k,</math>

<math>\tilde{G}_j^{(M)}:= \sum_{k=0}^j {j-k+M-1 \choose M-1} g_k.</math>

A particular (<math>M=n+1</math>) result is the identity

<math>\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)}.</math>

Here, <math display="inline">{n \choose k}</math> is the binomial coefficient.

Method

For two given sequences <math>(a_n) </math> and <math>(b_n) </math>, with <math>n \in \N</math>, one wants to study the sum of the following series: <math display="block">S_N = \sum_{n=0}^N a_n b_n</math>

If we define <math display="inline"> \displaystyle B_n = \sum_{k=0}^n b_k,</math> then for every <math>n>0, </math> <math>b_n = B_n - B_{n-1} </math> and <math display="block">S_N = a_0 b_0 + \sum_{n=1}^N a_n (B_n - B_{n-1}),</math> <math display="block">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}).</math>

Finally <math display="inline">\displaystyle S_N = a_N B_N - \sum_{n=0}^{N-1} B_n (a_{n+1} - a_n).</math>

This process, called an Abel transformation, can be used to prove several criteria of convergence for <math>S_N </math>.

Similarity with an integration by parts

The formula for an integration by parts is <math display="inline">\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</math>.

Beside the boundary conditions, we notice that the first integral contains two multiplied functions, one which is integrated in the final integral (<math>g' </math> becomes <math>g </math>) and one which is differentiated (<math>f </math> becomes <math>f' </math>).

The process of the Abel transformation is similar, since one of the two initial sequences is summed (<math>b_n </math> becomes <math>B_n </math>) and the other one is differenced (<math>a_n </math> becomes <math>a_{n+1} - a_n </math>).

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.
It may be used to prove Nicomachus's theorem that the sum of the first <math>n</math> cubes equals the square of the sum of the first <math>n</math> positive integers.<ref>Template:Cite journal</ref>
Summation by parts is frequently used to prove Abel's theorem and Dirichlet's test.
One can also use this technique to prove Abel's test: If <math display="inline">\sum_n b_n</math> is a convergent series, and <math>a_n</math> a bounded monotone sequence, then <math display="inline">S_N = \sum_{n=0}^N a_n b_n</math> converges.

Proof of Abel's test. Summation by parts gives <math display="block">\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}</math> where a is the limit of <math>a_n</math>. As <math display="inline">\sum_n b_n</math> is convergent, <math>B_N</math> is bounded independently of <math>N</math>, say by <math>B</math>. As <math>a_n-a</math> go to zero, so go the first two terms. The third term goes to zero by the Cauchy criterion for <math display="inline">\sum_n b_n</math>. The remaining sum is bounded by <math display="block">\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|</math> by the monotonicity of <math>a_n</math>, and also goes to zero as <math>N \to \infty</math>.

Using the same proof as above, one can show that if

the partial sums <math>B_N</math> form a bounded sequence independently of <math>N</math>;
<math>\sum_{n=0}^\infty |a_{n+1} - a_n| < \infty</math> (so that the sum <math>\sum_{n=N}^{M-1} |a_{n+1}-a_n|</math> goes to zero as <math>N</math> goes to infinity)
<math>\lim a_n = 0</math>

then <math display="inline">S_N = \sum_{n=0}^N a_n b_n</math> converges.

In both cases, the sum of the series satisfies:<math display="block"> |S| = \left|\sum_{n=0}^\infty a_n b_n \right| \le B \sum_{n=0}^\infty |a_{n+1}-a_n|.</math>