AOCP/Harmonic Numbers

Volume 1

Chapter 1: Basic Concepts: Harmonic numbers

Harmonic numbers become important in analyses of algorithms. Define

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