AOCP/Harmonic Numbers - Revision history

Admin: Fix math syntax error: change > to \geq in the inequality (non-strict, since 1/(2^m+2^m) = 1/2^{m+1}) (via update-page on MediaWiki MCP Server)

2026-06-06T01:22:25Z

Fix math syntax error: change > to \geq in the inequality (non-strict, since 1/(2^m+2^m) = 1/2^{m+1}) (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 01:22, 6 June 2026
Line 26:		Line 26:

	<math>		<math>
	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}}		H_{2^m} + \dfrac{1}{2^m+1} + \dfrac{1}{2^m + 2} + \dots + \dfrac{1}{2^{m+1}} \geq H_{2^m} + \dfrac{1}{2^{m+1}} + \dfrac{1}{2^{m + 1}} + \dots + \dfrac{1}{2^{m+1}}
	</math>		</math>

Admin: /* Chapter 1: Basic Concepts: Harmonic numbers */

2017-07-20T07:12:37Z

Chapter 1: Basic Concepts: Harmonic numbers

← Older revision		Revision as of 07:12, 20 July 2017
Line 11:		Line 11:
	While it does not occur often in classical mathematics, it crops up more often in algorithm analysis.		While it does not occur often in classical mathematics, it crops up more often in algorithm analysis.

			We can make <math>H_n</math> as large as we please from observing that

			<math>
			H_{2^m} \geq 1 + \dfrac{m}{2}
			</math>

			This results from the fact that

			<math>
			H_{2^{m+1}} = H_{2^m} + \dfrac{1}{2^m+1} + \dfrac{1}{2^m + 2} + \dots + \dfrac{1}{2^{m+1}}
			</math>

			Now we have,

			<math>
			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}}
			</math>

			and the right side is

			<math>
			H_{2^m} + \frac{1}{2}
			</math>

			therefore

			<math>
			H_{2^m} \geq 1 + \dfrac{m}{2}
			</math>

	=Flags=		=Flags=

Admin at 07:08, 20 July 2017

2017-07-20T07:08:38Z

← Older revision		Revision as of 07:08, 20 July 2017
Line 10:		Line 10:

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




			=Flags=

			{{AOCPFlag}}

			[[Category:Harmonic Numbers]]

Admin: Created page with "=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}..."$

2017-07-20T07:08:19Z

Created page with "=Volume 1= ==Chapter 1: Basic Concepts: Harmonic numbers== Harmonic numbers become important in analyses of algorithms. Define <math> H_n = 1 + \dfrac{1}{2} + \dfrac{1}{3}..."

New page

=Volume 1=

==Chapter 1: Basic Concepts: Harmonic numbers==

Harmonic numbers become important in analyses of algorithms. Define

<math>
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
</math>

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

AOCP/Harmonic Numbers - Revision history

Admin: Fix math syntax error: change > to \geq in the inequality (non-strict, since 1/(2^m+2^m) = 1/2^{m+1}) (via update-page on MediaWiki MCP Server)

Admin: /* Chapter 1: Basic Concepts: Harmonic numbers */

Admin at 07:08, 20 July 2017

Admin: Created page with "=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}..."

Admin: Created page with "=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}..."$