Discrete Sums to Continuous Integrals with Abel's Partial Summation Formula

It is often easier to understand how a discrete function behaves if it can be expressed as a continuous function. Abel's partial summation formula allows us to write a discrete sum as continuous integral.

In this blog post we'll derive the partial summation formula, and show a simple example of its power.

The video for this post is at [youtube], and the slides are here [pdf].

A Useful Object

The following is a sum over an arithmetic function $a(n)$ weighted by a smooth function $f(x)$. 

$$\sum _{x_1<n\le x_2}a(n)f(n)$$

This is a useful general object to find an integral form for, because it gives us flexibility in choosing the arithmetic and smooth functions. 

To be more precise about the functions, $a(n)$ takes only positive integers $n\ge 1$, and $f(x)$ has a continuous derivative over the domain $[x_1,x_2]$. Both $a(n)$ and $f(x)$ can be complex.

Deriving An Integral Form

If you look ahead, the derivation of an integral form for the sum might look overwhelming, but it is just lots of simple algebra.

Because $a(n)$ is only defined over integers $n\ge 1$, we can clarify the sum by setting $m_1=\lfloor x_1\rfloor$  and $m_2=\lfloor x_2\rfloor$. Remember that $\lfloor x\rfloor$  is the largest integer up to, and including, $x$.

$$\sum _{x_1<n\le x_2}a(n)f(n)=\sum _{n=m_1+1}^{m_2}a(n)f(n)$$

Let's define $A(x)=\sum _{n\le x}a(n)$. By definition $a(n)=A(n)-A(n-1)$ so we can replace $a(n)$.

$$\begin{array}{rl}\sum _{m_1+1}^{m_2}a(n)f(n)& =\sum _{m_1+1}^{m_2}[A(n)-A(n-1)]f(n)\\ \\ & =\sum _{m_1+1}^{m_2}A(n)f(n)-\sum _{m_1}^{m_2-1}A(n)f(n+1)\end{array}$$

The two sums have different limits for n, but both cover $[m_1+1,m_2-1]$.

$$\begin{array}{rl}\sum _{m_1+1}^{m_2}a(n)f(n)& =\sum _{m_1+1}^{m_2-1}A(n)[f(n)-f(n+1)]\\ \\ & +A(m_2)f(m_2)-A(m_1)f(m_1+1)\end{array}$$

Noticing that ${\int }_n^{n+1}{f}^{\prime }(t)dt=f(n+1)-f(n)$ allows us to introduce the integral.

$$\begin{array}{rl}\sum _{m_1+1}^{m_2}a(n)f(n)& =-\sum _{m_1+1}^{m_2-1}A(n){\int }_n^{n+1}{f}^{\prime }(t)dt\\ \\ & +A(m_2)f(m_2)-A(m_1)f(m_1+1)\end{array}$$

Now, because $A(t)=A(n)$ over the interval $[n,n+1)$, we can move $A(n)$ it inside the integral as $A(t)$.

$$\begin{array}{rl}\sum _{m_1+1}^{m_2}a(n)f(n)& =-\sum _{m_1+1}^{m_2-1}{\int }_n^{n+1}A(t)f^{\prime }(t)dt\\ \\ & +A(m_2)f(m_2)-A(m_1)f(m_1+1)\end{array}$$

That sum of integrals over consecutive intervals can be simplified to a single integral. 

$$\begin{array}{rl}\sum _{x_1<n\le x_2}a(n)f(n)& =-{\int }_{m_1+1}^{m_2}A(t)f^{\prime }(t)dt\\ \\ & +A(m_2)f(m_2)-A(m_1)f(m_1+1)\end{array}$$

We now need to adjust the integration limits back to $x_1$ and $x_2$, not forgetting the intervals to $m_1$ and $m_2$. Writing out the integrals that split the interval $[x_1,x_2]$ is helpful.

$${\int }_{x_1}^{x_2}Xdt={\int }_{m_1+1}^{m_2}Xdt+{\int }_{x_1}^{m_1+1}Xdt+{\int }_{m_2}^{x_2}Xdt$$

Rearranging, and noticing that $A(t)=A(x_1)$ over the interval $[x_1,m_1+1)$, and $A(t)=A(x_2)$ over the interval $[m_2,x_2]$, gives us the following.

$$\begin{array}{rl}-{\int }_{m_1+1}^{m_2}A(t)f^{\prime }(t)dt& ={\int }_{x_1}^{m_1+1}A(t)f^{\prime }(t)dt+{\int }_{m_2}^{x_2}A(t)f^{\prime }(t)dt\\ \\ & -{\int }_{x_1}^{x_2}A(t)f^{\prime }(t)dt\\ \\ & =A(x_1)[f(m_1+1)-f(x_1)]+A(x_2)[f(x_2)-f(m_2)]\\ \\ & -{\int }_{x_1}^{x_2}A(t)f^{\prime }(t)dt\end{array}$$

We plug this integral back into our object, then use $A(m_1)=A(x_1)$ and $A(m_2)=A(x_2)$.

$$\begin{array}{rl}\sum _{x_1<n\le x_2}a(n)f(n)& =A(x_2)f(m_2)-A(x_1)f(m_1+1)\\ \\ & +A(x_1)[f(m_1+1)-f(x_1)]+A(x_2)[f(x_2)-f(m_2)]\\ \\ & -{\int }_{x_1}^{x_2}A(t)f^{\prime }(t)dt\end{array}$$

Many of these terms cancel out, leaving us with the much neater Abel Identity, as it is also called.

$$\boxed{{\displaystyle \sum _{x_1<n\le x_2}a(n)f(n)=A(x_2)f(x_2)-A(x_1)f(x_1)-{\int }_{x_1}^{x_2}A(t)f^{\prime }(t)dt}}$$

In many cases $n$ starts at 1, and so the formula reduces further. 

$$\boxed{{\displaystyle \sum _{1\le n\le x_2}a(n)f(n)=A(x_2)f(x_2)-{\int }_1^{x_2}A(t)f^{\prime }(t)dt}}$$

The lower limit of the integral is 1 because $A(t)=0$ in the range $[0,1)$.

Example: Growth of $\sum 1/n$

Abel's identity is particularly useful for clarifying the asymptotic behaviour of discrete functions. Let's illustrate its use to show the how the harmonic series $\sum _1^{N}1/n$ grows.

We can choose $a(n)=1$ and $f(x)=1/x$, which means $A(x)=\lfloor x\rfloor$  and $f^{\prime }(x)=-1/x^2$. 

$$\begin{array}{rl}\sum _{n\le N}\frac{1}{n}& =A(N)f(N)-{\int }_1^{N}A(t)f^{\prime }t)\\ \\ & =\frac{N-\{N\}}{N}+{\int }_1^N\frac{t-\{t\}}{t^2}dt\end{array}$$

We've used $\lfloor x\rfloor =x-\{x\}$, where $\{x\}$ is the fractional part of $x$. This also lets us split the integral into manageable parts.

$$\sum _{0<n\le N}\frac{1}{n}=1+\mathcal{O}\left(\frac{1}{N}\right)+{\int }_1^N\frac{1}{t}dt-{\int }_1^N\frac{\{t\}}{t^2}dt$$

Because $\{t\}$ is only ever in the range $[0,1)$, the last integral is always less than ${\int }_1^{N}1/t^{2}dt$, that is, $\mathcal{O}\left({[-1/t]}_1^N\right)$.

$$\begin{array}{rl}\sum _{0<n\le N}\frac{1}{n}& =1+\mathcal{O}\left(\frac{1}{N}\right)+\ln (N)+\mathcal{O}(1-\frac{1}{N})\\ \\ & =\ln (N)+\mathcal{O}\left(1\right)\end{array}$$

This tells us the harmonic series grows like $\ln (N)$, a powerful result derived easily using the Abel identity. It also tells us the difference is bounded by 1. In fact, the difference tends to the Euler–Mascheroni constant $\gamma \approx 0.5772$ which pops up in several areas of number theory and analysis.