Summation by parts

Newton series

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

${\displaystyle \begin{array}{cc}\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{array}}$

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

${\displaystyle \begin{array}{cc}\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{array}}$

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}(\genfrac{}{}{0ex}{}{M}{k})f_{j+k}}$

and

${\displaystyle G_j^{(M)}:=\sum _{k=j}^n(\genfrac{}{}{0ex}{}{k-j+M-1}{M-1})g_k,}$

${\displaystyle {\tilde{G}}_j^{(M)}:=\sum _{k=0}^j(\genfrac{}{}{0ex}{}{j-k+M-1}{M-1})g_k.}$

A particular (${\displaystyle M=n+1}$) result is the 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, $(\genfrac{}{}{0ex}{}{n}{k})$ is the binomial coefficient.

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_1{B}_0+a_N{B}_N+\sum _{n=1}^{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}$.

Similarity with an integration by parts

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

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}$).

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 ${\displaystyle n}$ cubes equals the square of the sum of the first ${\displaystyle n}$ positive integers.
• 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 $\sum _n{b}_n$ is a convergent series, and ${\displaystyle a_n}$ a bounded monotone sequence, then $S_N=\sum _{n=0}^N{a}_n{b}_n$ converges.

Proof of Abel's test. Summation by parts gives $${\displaystyle \begin{array}{cc}{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{array}}$$ where a is the limit of ${\displaystyle a_n}$. As $\sum _n{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 $\sum _n{b}_n$. The remaining sum is bounded by $${\displaystyle \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 ${\displaystyle a_n}$, and also goes to zero as ${\displaystyle N\to \mathrm{\infty }}$.

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

1. the partial sums ${\displaystyle B_N}$ form a bounded sequence independently of ${\displaystyle N}$;
2. ${\displaystyle \sum _{n=0}^{\mathrm{\infty }}|a_{n+1}-a_n|<\mathrm{\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)
3. ${\displaystyle lim{a}_n=0}$

then $S_N=\sum _{n=0}^N{a}_n{b}_n$ converges.

In both cases, the sum of the series satisfies:$${\displaystyle |S|=\left|\sum _{n=0}^{\mathrm{\infty }}{a}_n{b}_n\right|\le B\sum _{n=0}^{\mathrm{\infty }}|a_{n+1}-a_n|.}$$

Summation-by-parts operators for high order finite difference methods

A summation-by-parts (SBP) finite difference operator conventionally consists of a centered difference interior scheme and specific boundary stencils that mimics behaviors of the corresponding integration-by-parts formulation. The boundary conditions are usually imposed by the Simultaneous-Approximation-Term (SAT) technique. The combination of SBP-SAT is a powerful framework for boundary treatment. The method is preferred for well-proven stability for long-time simulation, and high order of accuracy.