AOCP/Harmonic Numbers

Volume 1

Chapter 1: Basic Concepts: Harmonic numbers

Harmonic numbers become important in analyses of algorithms. Define

$ H_n = 1 + \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \dots + \dfrac{1}{n} = \sum_{1 \leq k \leq n} \dfrac{1}{k} \qquad n \geq 0 $

While it does not occur often in classical mathematics, it crops up more often in algorithm analysis.

We can make $ H_n $ as large as we please from observing that

$ H_{2^m} \geq 1 + \dfrac{m}{2} $

This results from the fact that

$ H_{2^{m+1}} = H_{2^m} + \dfrac{1}{2^m+1} + \dfrac{1}{2^m + 2} + \dots + \dfrac{1}{2^{m+1}} $

Now we have,

$ H_{2^m} + \dfrac{1}{2^m+1} + \dfrac{1}{2^m + 2} + \dots + \dfrac{1}{2^{m+1}} > H_{2^m} + \dfrac{1}{2^{m+1}} + \dfrac{1}{2^{m + 1}} + \dots + \dfrac{1}{2^{m+1}} $

and the right side is

$ H_{2^m} + \frac{1}{2} $

therefore

$ H_{2^m} \geq 1 + \dfrac{m}{2} $