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}}$