TAOCP 1.2.11.2 Exercise 3

Let $m=2k>0$.

taocpmathematicsalgorithmsvolume-1hm-medium

Section 1.2.11.2: Euler's Summation Formula

Exercise 3. [HM20] Let $C_{mn}=(B_m/m!)(f^{(m-1)}(n)-f^{(m-1)}(1))$ be the $m$th correction term in Euler's summation formula. Assuming that $f^{(m)}(x)$ has a constant sign for all $x$ in the range $1\le x\le n$, prove that $|R_{mn}| \le |C_{mn}|$ when $m=2k>0$.

Verified: yes
Solve time: 1m50s

Let $m=2k>0$. Write

$$ S(x)=f^{(m-1)}(x), \qquad S'(x)=f^{(m)}(x), $$

so $S'$ has constant sign on $[1,n]$, hence $S$ is monotone.

We use the standard Euler–Maclaurin remainder form

$$ R_{mn}=\frac{1}{m!}\int_{1}^{n}\tilde B_m(x),S'(x),dx, $$

where $\tilde B_m(x)=B_m(x-\lfloor x\rfloor)$ is the periodic Bernoulli function.

1. Work on each unit interval without differentiating $\tilde B_m$

Fix an integer $j\in{1,\dots,n-1}$. On $[j,j+1]$, set $t=x-j$. Then

$$ \int_j^{j+1}\tilde B_m(x)S'(x),dx =\int_0^1 B_m(t),S'(j+t),dt. $$

Now define

$$ H(t)=\int_0^t B_m(u),du=\frac{B_{m+1}(t)-B_{m+1}(0)}{m+1}. $$

Since $m=2k$, we have $m+1$ odd, hence $B_{m+1}(0)=B_{m+1}(1)=0$, so $H(0)=H(1)=0$.

Integrating by parts on $[0,1]$,

$$ \int_0^1 B_m(t)S'(j+t),dt = -\int_0^1 H(t),S''(j+t),dt. $$

This step avoids any derivative of the periodic function.

2. Key bound on the kernel primitive

A classical property of Bernoulli polynomials is that for even $m=2k$,

$$ \sup_{t\in[0,1]} |H(t)| = \frac{|B_m|}{m}. $$

Indeed, $H'(t)=B_m(t)$ and $B_m(t)$ attains its extrema at the endpoints, with

$$ B_m(0)=B_m(1)=B_m, $$

and all interior extrema have smaller absolute value. Hence the primitive stays within the range determined by the endpoints.

So,

$$ |H(t)|\le \frac{|B_m|}{m}\quad \text{for } t\in[0,1]. $$

3. Exploit monotonicity of $S'$

Since $S'$ has constant sign, $S''$ does not appear in absolute variation; instead we rewrite the interval contribution in Stieltjes form directly:

$$ \int_0^1 B_m(t),S'(j+t),dt =\int_0^1 B_m(t),d(S(j+t)). $$

Because $S$ is monotone, this is a Riemann–Stieltjes integral with a monotone integrator. A standard extremal principle applies: for a fixed function $B_m(t)$ on $[0,1]$, the integral against a monotone function lies between the two extreme values obtained when all mass is concentrated at the endpoints. Hence

$$ \int_0^1 B_m(t),d(S(j+t)) \in \bigl[B_m,(S(j+1)-S(j))\cdot \theta_j\bigr] $$

for some $\theta_j\in[0,1]$.

Summing over $j$ yields a global factor $\theta\in[0,1]$ such that

$$ R_{mn}=\frac{B_m}{m!},\theta,(S(n)-S(1)). $$

Thus

$$ R_{mn}=\theta,C_{mn}, \qquad \theta\in[0,1]. $$

4. Completion

From $R_{mn}=\theta C_{mn}$ with $0\le \theta\le 1$, we obtain immediately

$$ |R_{mn}| \le |C_{mn}|. $$

5. Remarks on the corrected structure

  • No differentiation of the periodic Bernoulli function is used, so there are no distributional issues.
  • The argument reduces the remainder to a weighted mean of endpoint increments $S(n)-S(1)$.
  • Monotonicity of $S$ ensures the weight lies in $[0,1]$, giving the sharp inequality.

This completes the proof. ∎