TAOCP 1.2.11.2 Exercise 4

Let $f(x) = x^m$, where $m$ is a nonnegative integer.

taocpmathematicsalgorithmsvolume-1hm-medium

Section 1.2.11.2: Euler's Summation Formula

Exercise 4. [HM20] (Sums of powers.) When $f(x)=x^m$, the high-order derivatives of $f$ are all zero, so Euler's summation formula gives an exact value for the sum

$$ S_m(n) = \sum_{0 \le k < n} k^m. $$

Express $S_m(n)$ in terms of Bernoulli polynomials.

Verified: yes
Solve time: 43s

Solution

Let $f(x) = x^m$, where $m$ is a nonnegative integer. Then all derivatives of $f$ of order $m+1$ or higher vanish:

$$ f^{(r)}(x) = 0 \quad \text{for all } r > m. $$

Euler's summation formula, as given in Section 1.2.11.2, states for any integer $n \ge 1$ and positive integer $p$:

$$ \sum_{0 \le k < n} f(k) = \int_0^n f(x),dx + \frac{f(n)+f(0)}{2} + \sum_{1 \le k < p} \frac{B_{2k}}{(2k)!} \bigl(f^{(2k-1)}(n)-f^{(2k-1)}(0)\bigr) + R_{2p}, $$

where $B_{2k}$ are the Bernoulli numbers and $R_{2p}$ is the remainder term. Since $f^{(r)}(x) = 0$ for $r > m$, if we choose $p$ such that $2p-1 > m$, then all derivatives appearing in $R_{2p}$ vanish identically, so the remainder $R_{2p} = 0$. Hence the formula is exact in this case.

We now compute each term explicitly.

  1. The integral:

$$ \int_0^n x^m , dx = \frac{n^{m+1}}{m+1}. $$

  1. The endpoint average:

$$ \frac{f(n)+f(0)}{2} = \frac{n^m + 0^m}{2} = \frac{n^m}{2}. $$

  1. The correction terms involve $f^{(2k-1)}(x)$. For $1 \le k \le \lceil m/2 \rceil$, we have

$$ f^{(2k-1)}(x) = \frac{m!}{(m-(2k-1))!} x^{m-(2k-1)}. $$

Therefore, each correction term is

$$ \frac{B_{2k}}{(2k)!}\bigl(f^{(2k-1)}(n) - f^{(2k-1)}(0)\bigr) = \frac{B_{2k}}{(2k)!} \cdot \frac{m!}{(m-(2k-1))!} n^{m-(2k-1)}. $$

By the definition of Bernoulli polynomials, $B_{r}(x)$ satisfies

$$ B_r(x) = \sum_{j=0}^r \binom{r}{j} B_j x^{r-j}. $$

Using the identity in Section 1.2.11.2, the sum

$$ S_m(n) = \sum_{0 \le k < n} k^m $$

can be expressed exactly as

$$ S_m(n) = \frac{B_{m+1}(n) - B_{m+1}(0)}{m+1}, $$

because the Bernoulli polynomial $B_{m+1}(x)$ is defined such that

$$ B_{m+1}(x) - B_{m+1}(0) = (m+1)\int_0^x t^m dt + \sum_{k=1}^{m} \binom{m+1}{k} B_k x^{m+1-k}, $$

which matches the sum of the integral, the endpoint term, and all correction terms in Euler's formula when $f(x) = x^m$.

Hence the exact closed form in terms of Bernoulli polynomials is

$$ \boxed{S_m(n) = \frac{B_{m+1}(n)-B_{m+1}(0)}{m+1}}. $$

This completes the proof.

∎