TAOCP 1.2.7 Exercise 3

Let H_n^{(r)}=\sum_{k=1}^{n}\frac{1}{k^r}, \qquad r>1.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.7: Harmonic Numbers

Exercise 3. [M21] Generalize the argument used in the previous exercise to show that, for $r>1$, the sum $H_n^{(r)}$ remains bounded for all $n$. Find an upper bound.

Verified: no
Solve time: -

Solution

Let

$$ H_n^{(r)}=\sum_{k=1}^{n}\frac{1}{k^r}, \qquad r>1. $$

Exercise 2 treated the case $r=1$ by grouping terms between powers of $2$. The same argument applies here.

Choose an integer $m$ such that

$$ 2^m \le n < 2^{m+1}. $$

Then

$$ H_n^{(r)} \le H_{2^{m+1}}^{(r)} =1+\sum_{k=2}^{2^{m+1}}\frac{1}{k^r}. $$

Partition the sum into dyadic blocks:

$$ H_{2^{m+1}}^{(r)} = 1 +\sum_{1\le k<2}\frac{1}{k^r} +\sum_{2\le k<4}\frac{1}{k^r} +\cdots +\sum_{2^m\le k<2^{m+1}}\frac{1}{k^r}. $$

For each block $2^j\le k<2^{j+1}$, there are exactly $2^j$ terms, and each satisfies

$$ \frac{1}{k^r}\le \frac{1}{(2^j)^r}. $$

Hence

$$ \sum_{2^j\le k<2^{j+1}}\frac{1}{k^r} \le 2^j\frac{1}{(2^j)^r} = \frac{1}{2^{j(r-1)}}. $$

Therefore

$$ H_{2^{m+1}}^{(r)} \le 1+\sum_{j=0}^{m}\frac{1}{2^{j(r-1)}}. $$

Since $r>1$, the ratio

$$ \frac{1}{2^{r-1}} $$

lies strictly between $0$ and $1$. The finite geometric sum is bounded by the corresponding infinite sum:

$$ \sum_{j=0}^{m}\frac{1}{2^{j(r-1)}} < \sum_{j=0}^{\infty}\frac{1}{2^{j(r-1)}} = \frac{1}{1-2^{1-r}}. $$

Thus

$$ H_n^{(r)} < 1+\frac{1}{1-2^{1-r}} \qquad (n\ge 1). $$

Hence $H_n^{(r)}$ remains bounded for all $n$ when $r>1$. An upper bound is

$$ \boxed{ H_n^{(r)} < 1+\frac{1}{1-2^{1-r}} }. $$

This completes the proof.

∎