AOCP/Harmonic Numbers

Volume 1

Chapter 1: Basic Concepts: Harmonic numbers

Harmonic numbers become important in analyses of algorithms. Define

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle H_n} as large as we please from observing that

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle H_{2^m} \geq 1 + \dfrac{m}{2} }

This results from the fact that

Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle H_{2^m} + \frac{1}{2} }

therefore

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle H_{2^m} \geq 1 + \dfrac{m}{2} }