TAOCP 1.2.11.2 Exercise 1

We are asked to **prove Eq.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.11.2: Euler's Summation Formula

Exercise 1. [M18] Prove Eq. (7).

Verified: yes
Solve time: 1m44s

Corrected Solution

We are asked to prove Eq. (7) of Section 1.2.11.2, which is the Euler–Maclaurin summation formula:

$$ \sum_{k=m}^{n} f(k) = \int_m^n f(x),dx + \frac{f(m)+f(n)}{2} + \sum_{r=1}^{p} \frac{B_{2r}}{(2r)!}\bigl(f^{(2r-1)}(n)-f^{(2r-1)}(m)\bigr) + R_p, $$

where $B_{2r}$ are Bernoulli numbers, $f^{(r)}$ is the $r$-th derivative of $f$, and $R_p$ is a remainder term.

We give a rigorous derivation.

Step 1: Express the sum as an integral plus a periodic correction

Let ${x} = x - \lfloor x \rfloor$ denote the fractional part of $x$. Define the first Bernoulli function

$$ B_1(x) = x - \frac{1}{2}, \quad 0 \le x < 1, $$

and extend periodically to all $x$ by $B_1(x+1) = B_1(x)$. Then

$$ B_1(x) = {x} - \frac{1}{2}. $$

For any smooth $f$, the Euler summation formula starts from

$$ \sum_{k=m}^{n} f(k) = \int_m^n f(x),dx + \int_m^n f'(x) B_1(x),dx. \tag{1} $$

Justification: For integer $k$,

$$ f(k) = \int_{k}^{k+1} f(x),dx + \int_{k}^{k+1} f'(x)(k-x),dx. $$

Summing over $k = m, \dots, n-1$ and writing $k-x = -B_1(x) - \tfrac{1}{2}$ yields (1).

Step 2: Integration by parts to generate Bernoulli-number terms

We integrate $\int_m^n f'(x) B_1(x),dx$ by parts:

$$ \int_m^n f'(x) B_1(x),dx = \bigl[f(x) B_1(x)\bigr]_m^n - \int_m^n f(x) B_1'(x),dx. \tag{2} $$

Since $B_1'(x) = 1$ almost everywhere except at integers (a set of measure zero, harmless for the integral):

$$ \int_m^n f(x) B_1'(x),dx = \int_m^n f(x),dx. $$

Therefore, from (1) and (2):

$$ \sum_{k=m}^{n} f(k) = \int_m^n f(x),dx + \bigl[f(x) B_1(x)\bigr]_m^n - \int_m^n f(x),dx = f(n) B_1(n) - f(m) B_1(m). \tag{3} $$

Using $B_1(n) = 1/2$ and $B_1(m) = -1/2$ (since $B_1(k) = k-\frac12$):

$$ \sum_{k=m}^{n} f(k) = \frac{f(n)+f(m)}{2} + \int_m^n f(x),dx. \tag{4} $$

This recovers the trapezoidal rule as the first approximation. To go further, we iterate integration by parts.

Step 3: Iterated integration by parts using higher Bernoulli polynomials

Define the Bernoulli polynomials $B_r(x)$ by

$$ B_0(x) = 1, \quad \frac{d}{dx} B_r(x) = r B_{r-1}(x), \quad \int_0^1 B_r(x),dx = 0 \text{ for } r \ge 1. $$

Set $B_r = B_r(0)$ as the Bernoulli numbers. Then, for $r \ge 1$,

$$ \int_m^n f^{(r)}(x) B_r({x}),dx = \bigl[f^{(r-1)}(x) B_r({x})\bigr]m^n - r \int_m^n f^{(r-1)}(x) B{r-1}({x}),dx. \tag{5} $$

Applying (5) repeatedly $p$ times, starting from $\int_m^n f'(x) B_1(x),dx$, produces

$$ \sum_{k=m}^{n} f(k) = \int_m^n f(x),dx + \frac{f(n)+f(m)}{2} + \sum_{r=1}^{p} \frac{B_{2r}}{(2r)!} \left(f^{(2r-1)}(n) - f^{(2r-1)}(m)\right) + R_p, \tag{6} $$

where

$$ R_p = \frac{1}{(2p)!} \int_m^n f^{(2p)}(x) B_{2p}({x}),dx. $$

Remarks:

  1. Odd-index Bernoulli numbers vanish except $B_1$. This is why only even indices appear in the sum.
  2. The remainder $R_p$ is bounded by

$$ |R_p| \le \frac{2 \zeta(2p)}{(2\pi)^{2p}} \max_{x\in[m,n]} |f^{(2p)}(x)|, $$

where $\zeta$ is the Riemann zeta function.

Step 4: Conclusion

We have derived Euler–Maclaurin summation formula rigorously using:

  • the first Bernoulli function $B_1(x)$ for the initial integral correction,
  • repeated integration by parts with Bernoulli polynomials to generate higher-order endpoint terms,
  • the standard definitions of Bernoulli numbers for coefficients.

Equation (6) coincides with Eq. (7) in Section 1.2.11.2, completing the proof.

∎

References for Bernoulli properties:

  • $B_0(x) = 1$, $B_1(x) = x - 1/2$, $B_r'(x) = r B_{r-1}(x)$
  • $\int_0^1 B_r(x),dx = 0$ for $r \ge 1$
  • $B_1 = -1/2$, $B_{2r+1} = 0$ for $r \ge 1$

This derivation properly explains the appearance of Bernoulli-number corrections and the remainder term.