TAOCP 1.2.7 Exercise 2

The argument in the text groups the terms of $H_{2^m}$ as follows: H_{2^m} = 1 + \frac12 + \left(\frac13 + \frac14\right) + \left(\frac15 + \cdots + \frac18\right)

taocpmathematicsalgorithmsvolume-1simple

Section 1.2.7: Harmonic Numbers

Exercise 2. [13] Show that the simple argument used in the text to prove that $H_{2^m} \ge 1 + m/2$ can be slightly modified to prove that $H_{2^m} \le 1 + m$.

Verified: no
Solve time: -

Solution

The argument in the text groups the terms of $H_{2^m}$ as follows:

$$ H_{2^m} = 1 + \frac12

  • \left(\frac13 + \frac14\right)
  • \left(\frac15 + \cdots + \frac18\right)
  • \cdots
  • \left(\frac{1}{2^{m-1}+1} + \cdots + \frac1{2^m}\right). $$

For each integer $r$ with $1 \le r \le m-1$, the block

$$ \frac{1}{2^r+1} + \frac{1}{2^r+2} + \cdots + \frac1{2^{r+1}} $$

contains exactly $2^r$ terms. Every denominator in this block is at least $2^r+1$, hence every term is at most $1/2^r$. Therefore

$$ \frac{1}{2^r+1} + \frac{1}{2^r+2} + \cdots + \frac1{2^{r+1}} \le 2^r \cdot \frac1{2^r} = 1. $$

Applying this estimate to each block gives

$$ H_{2^m} \le 1 + \frac12 + \underbrace{1 + 1 + \cdots + 1}_{m-1\text{ times}}. $$

The sum on the right-hand side equals

$$ 1 + \frac12 + (m-1) = m + \frac12. $$

Since $m+\frac12 \le 1+m$, we obtain

$$ H_{2^m} \le 1+m. $$

Thus the modified argument proves

$$ \boxed{H_{2^m} \le 1+m}. $$

∎