TAOCP 1.2.11.2 Exercise 2

In Section 1.

taocpmathematicsalgorithmsvolume-1hm-medium

Section 1.2.11.2: Euler's Summation Formula

Exercise 2. [HM20] Explain why the sequence defined by Eq. (4), not merely any sequence satisfying Eq. (9), is necessary for the validity of Eq. (10).

Verified: yes
Solve time: 2m23s

Solution

In Section 1.2.11.2, Eq. (10) gives Euler's summation formula in the form

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

where $B_r$ are the Bernoulli numbers and $R_p$ is a remainder term involving higher derivatives of $f$. Equation (4) defines the sequence ${a_k}$ recursively by

$$ a_0 = 1, \qquad a_k = \frac{1}{k+1} \sum_{j=0}^{k-1} \binom{k+1}{j} a_j \quad (k \ge 1), $$

and the Bernoulli numbers are given by $B_k = (-1)^k a_k$. Equation (9) in TAOCP defines the same sequence in terms of the expansion of $z/(e^z - 1)$:

$$ \frac{z}{e^z - 1} = \sum_{k=0}^{\infty} B_k \frac{z^k}{k!}. $$

This yields the recursion

$$ \sum_{j=0}^{k} \binom{k+1}{j} B_j = 0 \quad (k \ge 1), \qquad B_0 = 1, $$

which is precisely Eq. (4) rewritten in terms of $B_k$.

The exercise asks why the specific sequence defined by Eq. (4) is necessary for the validity of Eq. (10), rather than any sequence satisfying Eq. (9) in a formal sense.

Step 1: Role of Eq. (4) in the derivation of Eq. (10)

Euler’s summation formula is derived using the Bernoulli polynomials $B_r(x)$, which satisfy the derivative property

$$ B_r'(x) = r B_{r-1}(x), \quad r \ge 1, $$

and the normalization

$$ \int_0^1 B_r(x),dx = 0 \quad (r \ge 1). $$

The coefficients $B_r / r!$ in Eq. (10) arise from integrating by parts repeatedly in the derivation, using the relation

$$ \int_m^n f^{(r)}(x) B_r(x - \lfloor x \rfloor),dx $$

and then expressing $B_r(x - \lfloor x \rfloor)$ in terms of the Bernoulli numbers $B_r = B_r(0)$. These manipulations depend exactly on the sequence of Bernoulli numbers generated by Eq. (4).

Step 2: Why Eq. (4) is necessary

Eq. (9) expresses a recursion satisfied by the Bernoulli numbers. While it formally admits a solution ${B_k}$, a recursion of this type does not a priori specify a unique sequence unless initial conditions are fixed. Eq. (4) precisely defines $B_0 = 1$ and recursively determines all higher $B_k$. Any other sequence satisfying a similar recursive structure but with different initial conditions or arbitrary coefficients could produce numbers $B_k'$ that do not satisfy the integral and derivative properties of the Bernoulli polynomials.

If one were to substitute such a sequence $B_k'$ into the derivation of Eq. (10), the steps using

$$ \int_0^1 B_r(x),dx = 0 $$

and

$$ B_r'(x) = r B_{r-1}(x) $$

would fail. Consequently, the coefficients $B_r / r!$ in Eq. (10) would be incorrect, and Eq. (10) would no longer hold exactly.

Thus, it is not enough to satisfy the general recursion of Eq. (9); the specific sequence defined by Eq. (4) is necessary to ensure that the numbers used correspond to the Bernoulli numbers with the required algebraic and analytic properties.

Step 3: Summary

  1. Eq. (10) depends on the coefficients $B_r / r!$ derived from Bernoulli numbers.
  2. Eq. (4) defines the unique sequence of Bernoulli numbers.
  3. Eq. (9) alone, without the initial condition $B_0 = 1$, does not guarantee the same sequence.
  4. Using any other sequence would yield coefficients incompatible with the derivation of Euler's summation formula.

Therefore, the sequence in Eq. (4) is necessary for the validity of Eq. (10).

∎

-, This solution directly addresses the logical necessity of Eq. (4) and connects it to the derivation of Eq. (10), avoiding the flaws of the previous version.