Summation by Parts (Abel Transformation)

Summation by parts is the discrete counterpart of integration by parts. Instead of differentiating one factor and integrating the other, we take differences of one sequence and partial sums of the other.

This note revises my original Chinese article. A concise Chinese explanation follows the English proof.

Formula and proof

Let $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$ be real or complex numbers, with $n\ge1$ . Define

B_0=0,\qquad B_i=\sum_{j=1}^{i}b_j.

Then

\boxed{\sum_{i=1}^{n}a_ib_i =a_nB_n+\sum_{i=1}^{n-1}(a_i-a_{i+1})B_i.}

Since $b_i=B_i-B_{i-1}$ ,

\begin{aligned} \sum_{i=1}^{n}a_ib_i &=\sum_{i=1}^{n}a_iB_i-\sum_{i=1}^{n}a_iB_{i-1}\\ &=a_nB_n+\sum_{i=1}^{n-1}a_iB_i -\sum_{i=1}^{n-1}a_{i+1}B_i. \end{aligned}

Combining the last two sums proves the formula. The term involving $B_0$ vanishes. When $n=1$ , the sum from $1$ to $n-1$ is empty and the identity still holds.

Example: the sum of squares

Set $a_i=b_i=i$ , so $B_i=i(i+1)/2$ and $a_i-a_{i+1}=-1$ . Writing $S_n=\sum_{i=1}^{n}i^2$ , we obtain

S_n=\frac{n^2(n+1)}2-\frac12\sum_{i=1}^{n-1}(i^2+i).

The right side still contains a sum of squares, but this is an equation we can solve for $S_n$ . Substitute $\sum_{i=1}^{n-1}i^2=S_n-n^2$ and $\sum_{i=1}^{n-1}i=n(n-1)/2$ :

\begin{aligned} S_n&=\frac{n^2(n+1)}2-\frac{S_n-n^2}{2}-\frac{n(n-1)}4,\\ 3S_n&=n^2(n+1)+n^2-\frac{n(n-1)}2. \end{aligned}

Therefore

\boxed{S_n=\frac{n(n+1)(2n+1)}6.}

The partial-sum formula is especially useful when the $B_i$ are simple or bounded and the differences $a_i-a_{i+1}$ are easier to handle than the original products.

中文说明

原文发表于我的 Bilibili 专栏。本页修正了原推导中的求和指标与相邻项下标。

令 $B_0=0$ 、 $B_i=\sum_{j=1}^{i}b_j$ ，则 $b_i=B_i-B_{i-1}$ 。代入后，把第二个求和的指标平移一位，就得到

\sum_{i=1}^{n}a_ib_i =a_nB_n+\sum_{i=1}^{n-1}(a_i-a_{i+1})B_i.

这就是 Abel 变换，也称分部求和。它把 $b_i$ 换成部分和 $B_i$ ，同时把 $a_i$ 换成相邻项之差；端点项 $a_nB_n$ 不能漏掉。

证明平方和公式时，取 $a_i=b_i=i$ ，利用 $B_i=i(i+1)/2$ ，即可得到上面的关于 $S_n$ 的方程。右边再次出现 $S_n$ 并不意味着循环论证：把它移到左边，便能解出 $S_n=n(n+1)(2n+1)/6$ 。

另可参看究尽数学的 Abel 公式几何解释。