Analytic Number Theory/Useful summation formulas

Analytic number theory is so abysmally complex that we need a basic toolkit of summation formulas first in order to prove some of the most basic theorems of the theory.

Abel's summation formula

Theorem 1.1 (Abel's summation formula, also called Abel's identity):

Let $(a_{n})_{n\in \mathbb {N} }$ be a sequence and let $f:\mathbb {R} \to \mathbb {R}$ be a differentiable function such that $f'$ is Riemann integrable. If we define

$A(x):=\sum _{1\leq n\leq x}a_{n}$,

then we have

$\sum _{1\leq n\leq x}a_{n}f(n)=A(x)f(x)-\int _{1}^{x}A(y)f'(y)dy$.

Note: We need the Riemann integrability to be able to apply the fundamental theorem of calculus.

Proof 1:

We prove the theorem by induction on $\lfloor x\rfloor$.

1. $\lfloor x\rfloor =1$:

First, we have in this case

$\sum _{1\leq n\leq x}a_{n}f(n)=a_{1}f(1)$.

Then, we have

$A(x)f(x)=a_{1}f(x)=a_{1}f(1)-a_{1}(f(1)-f(x))=a_{1}f(1)+\int _{1}^{x}A(y)f'(y)dy$

by the fundamental theorem of calculus.

2. Induction step:

Define $N:=\lfloor x\rfloor$. We have

${\begin{aligned}\sum _{1\leq n\leq x}a_{n}f(n)&=\sum _{1\leq n\leq x-1}a_{n}f(n)+a_{N}f(N)\\&=A(x-1)f(x-1)-\int _{1}^{x-1}A(y)f'(y)dy+a_{N}f(N)\end{aligned}}$

by the induction hypothesis. Further,

${\begin{aligned}-\int _{1}^{x-1}A(y)f'(y)dy&=-\int _{1}^{x}A(y)f'(y)dy+\int _{x-1}^{x}A(y)f'(y)dy\\&=-\int _{1}^{x}A(y)f'(y)dy+\int _{x-1}^{N}A(y)f'(y)dy+\int _{N}^{x}A(y)f'(y)dy\\&=-\int _{1}^{x}A(y)f'(y)dy+A(N-1)\int _{x-1}^{N}f'(y)dy+A(N)\int _{N}^{x}f'(y)dy\\&=-\int _{1}^{x}A(y)f'(y)dy+A(N-1)(f(N)-f(x-1))+A(N)(f(x)-f(N))\end{aligned}}$.

Putting things together, we obtain

$\sum _{1\leq n\leq x}a_{n}f(n)=A(x-1)f(x-1)-\int _{1}^{x}A(y)f'(y)dy+A(N-1)(f(N)-f(x-1))+A(N)(f(x)-f(N))+a_{N}f(N)$

and thus the desired formula.

The method of proof we applied here was using induction and then trying to express the terms from the induction hypothesis in terms of the terms from the desired formula.$\Box$

Proof 2:

We prove the theorem by direct manipulation of the term on the left.

Define $k:=\lfloor x\rfloor$.

${\begin{aligned}\sum _{1\leq n\leq x}a_{n}f(n)&=\sum _{1\leq n\leq x}(A(n)-A(n-1))f(n)\\&=\sum _{1\leq n\leq x}A(n)f(n)-\sum _{0\leq n\leq x-1}A(n)f(n+1)=\sum _{1\leq n\leq x}A(n)f(n)-\sum _{1\leq n\leq x-1}A(n)f(n+1)\\&=\sum _{1\leq n\leq x-1}A(n)(f(n)-f(n+1))+A(k)f(k)\\&=\sum _{1\leq n\leq x-1}A(n)\left(-\int _{n}^{n+1}f'(t)dt\right)+A(x)f(x)-\int _{k}^{x}A(t)f'(t)dt\end{aligned}}$$\Box$

Proof 3:

We prove the formula by the means of the Riemann-Stieltjes integral. Indeed, by integration by parts, we have

${\begin{aligned}\sum _{1\leq n\leq x}a_{n}f(n)=\int _{0}^{x}f(t)dA(t)&=A(x)f(x)-\int _{0}^{x}A(t)df(t)\\&=A(x)f(x)-\int _{1}^{x}A(t)f'(t)dt\end{aligned}}$.$\Box$

Corollary 1.2:

$\sum _{y<n\leq x}a_{n}f(n)=A(x)f(x)-A(y)f(y)-\int _{y}^{x}A(t)f'(t)dt$.

Proof 1:

We deduce the formula from integration by parts for the Riemann-Stieltjes integral.

${\begin{aligned}\sum _{y<n\leq x}a_{n}f(n)=\int _{y}^{x}f(t)dA(t)&=f(x)A(x)-f(y)A(y)-\int _{y}^{x}A(t)df(t)\\&=f(x)A(x)-f(y)A(y)-\int _{y}^{x}A(t)f'(t)dt\end{aligned}}$$\Box$

Proof 2:

We directly manipulate the LHS (left hand side).

Define $k:=\lfloor x\rfloor$ and $m:=\lfloor y\rfloor$.

${\begin{aligned}\sum _{y<n\leq x}a_{n}f(n)&=\sum _{y<n\leq x}(A(n)-A(n-1))f(n)\\&=\sum _{y<n\leq x}A(n)f(n)-\sum _{y-1<n\leq x-1}A(n)f(n+1)\\&=\sum _{y<n\leq x-1}A(n)(f(n)-f(n+1))-A(m)f(m)+A(k)f(k)\\&=\sum _{y<n\leq x-1}A(n)-\left(\int _{n}^{n+1}f'(t)dt\right)-A(y)f(y)+A(x)f(x)-\int _{y}^{m}A(t)f'(t)dt-\int _{k}^{x}A(t)f'(t)dt\end{aligned}}$$\Box$

Two further proofs are given in exercises 1.1.1 and 1.1.5.

We note that induction and direct manipulation are quicker proofs for theorem 1.1, while corollary 1.2 is quicker proven from theorem 1.1 or Riemann-Stieltjes integration.

Exercises

• Exercise 1.1.1: Prove corollary 1.2 from theorem 1.1. Hint: $\sum _{y<n\leq x}a_{n}f(n)=\sum _{1\leq n\leq x}a_{n}f(n)-\sum _{1<n\leq y}a_{n}f(n)$.
• Exercise 1.1.2: Compute $\sum _{n=1}^{N}n^{3}$. Hint: Use $a_{n}=n$, $f(x)=x^{2}$, apply Abelian summation and split the resulting integral into pieces where $A(t)$ is constant. Then apply a similar process.
• Exercise 1.1.3: Prove that the limit $\lim _{n\to \infty }\left(-\log(n)+\sum _{k=1}^{n}{\frac {1}{k}}\right)$ exists. This limit is called the Euler–Mascheroni constant. Hint: Use $a_{n}=1$ and $f(x)={\frac {1}{x}}$.
• Exercise 1.1.4: Prove theorem 1.1 from corollary 1.2.
• Exercise 1.1.5: Prove corollary 1.2 using induction on $\lfloor x\rfloor$.

Euler's summation formula

Definition 1.3:

For $x\in \mathbb {R}$, we define

$\{x\}:=x-\lfloor x\rfloor$.

Theorem 1.4 (Euler's summation formula):

Let $f:\mathbb {R} \to \mathbb {R}$ be a differentiable function, such that $f'$ is Riemann integrable. Then

$\sum _{y<n\leq x}f(n)=\{x\}f(x)-\{y\}f(y)+\int _{y}^{x}f(t)dt+\int _{y}^{x}\{t\}f'(t)dt$.

Proof:

We prove the theorem from Corollary 1.2, setting $a_{n}=1$ and using integration by parts (integration by parts is proven using the fundamental theorem of calculus).

Indeed,

${\begin{aligned}\sum _{y<n\leq x}f(n)&=\lfloor x\rfloor f(x)-\lfloor y\rfloor f(y)-\int _{y}^{x}\lfloor t\rfloor f'(t)dt\\&=\lfloor x\rfloor f(x)-\lfloor y\rfloor f(y)-\int _{y}^{x}tf'(t)dt+\int _{y}^{x}\{t\}f'(t)dt\\&=\{x\}f(x)-\{y\}f(y)+\int _{y}^{x}f(t)dt+\int _{y}^{x}\{t\}f'(t)dt\end{aligned}}$,

where in the last line we used integration by parts on the integral $\int _{y}^{x}tf'(t)dt$.$\Box$

Corollary 1.5:

Exercises

1. Prove corollary 1.5.

Euler–Maclaurin formula

Theorem 1.6 (Euler–Maclaurin formula):

Define the functions $\rho (x):={\frac {1}{2}}-x$ and $\sigma (x):=\int _{0}^{x}\rho (y)dy$. Then for any twice continuously differentiable function $f$ such that $f''$ is Riemann integrable, we have

$\sum _{y<n\leq x}f(n)=\int _{x}^{y}f(t)dt+\rho (y)f(y)-\rho (x)f(x)+\sigma (x)f'(x)-\sigma (y)f'(y)+\int _{x}^{y}\sigma (t)f''(t)dt$.

Proof 1:

We prove the theorem by direct computation.

${\begin{aligned}\end{aligned}}$

Proof 2:

We prove the theorem from Euler's summation formula.