Proof that harmonic numbers grow like log n

Builds on Harmonic number Natural logarithm Integral of 1/x Logarithm of a quotient Quotient of continuous functions is continuous Continuous functions are Riemann integrable Integral of a power Linearity of the integral Monotonicity of the integral Monotone sequence Monotone convergence theorem for sequences Limits preserve non-strict inequalities Archimedean property The exponential function is strictly increasing Little o notation Asymptotic equivalence

Proof

We compare each term $\frac{1}{k}$ with the integral of $\frac{1}{t}$ over $[k, k + 1]$ , and use the monotone convergence theorem.

For each integer $n \ge 1$ , let $H_n$ be the $n$ -th harmonic number, and let $a_n = H_n - \ln n$ . Here $\ln$ is the natural logarithm.
Let $k \ge 1$ be an integer. By the integral of 1/x and the logarithm of a quotient, $\int_k^{k+1} \frac{dt}{t} = \ln \frac{k+1}{k} = \ln(k + 1) - \ln k$ .
The function $t \mapsto \frac{1}{t}$ is continuous on $[k, k + 1]$ , by continuity of quotients. So it is Riemann integrable there, since continuous functions are Riemann integrable.
For a constant $c$ , the integral of a power with exponent $0$ and linearity of the integral give $\int_k^{k+1} c \, dt = c$ .
For $t \in [k, k + 1]$ , we have $\frac{1}{k + 1} \le \frac{1}{t} \le \frac{1}{k}$ .
By monotonicity of the integral and steps 2 to 5, $\frac{1}{k + 1} \le \ln(k + 1) - \ln k \le \frac{1}{k}.$
For $n \ge 1$ , $a_{n+1} - a_n = \frac{1}{n + 1} - (\ln(n + 1) - \ln n)$ . This is $\le 0$ by the left inequality of step 6 with $k = n$ . So $(a_n)$ is decreasing.
Since $e^0 = 1$ , the definition of $\ln$ gives $\ln 1 = 0$ .
Summing the right inequality of step 6 over $k = 1, \dots, n$ gives a telescoping sum: $\ln(n + 1) - \ln 1 \le H_n$ . By step 8, $\ln(n + 1) \le H_n$ .
By step 9 and step 6 with $k = n$ , $a_n \ge \ln(n + 1) - \ln n \ge \frac{1}{n + 1} > 0$ . So $(a_n)$ is bounded below by $0$ .
The sequence $(-a_n)$ is increasing by step 7, and bounded above by $0$ by step 10.
By the monotone convergence theorem, $(-a_n)$ converges. So $(a_n)$ converges to some real number $\gamma$ .
By step 8, $a_1 = 1 - \ln 1 = 1$ . By steps 7 and 10, $0 \le a_n \le 1$ for all $n \ge 1$ .
Since limits preserve non-strict inequalities, step 13 gives $0 \le \gamma \le 1$ . So the limit exists and lies in $[0, 1]$ .
It remains to show $H_n \sim \ln n$ . Let $\varepsilon > 0$ . By the Archimedean property, there is an integer $N \ge 2$ with $N > e^{1/\varepsilon}$ .
Let $n \ge N$ . Suppose that $\ln n < \frac{1}{\varepsilon}$ . Since the exponential function is strictly increasing, $n = e^{\ln n} < e^{1/\varepsilon} < N$ . This contradicts $n \ge N$ .
So $\ln n \ge \frac{1}{\varepsilon} > 0$ for all $n \ge N$ . With step 13, $|H_n - \ln n| = a_n \le 1 \le \varepsilon \ln n$ for all $n \ge N$ .
By the definition of little o notation, step 17 says $H_n - \ln n = o(\ln n)$ . This is the definition of asymptotic equivalence, so $H_n \sim \ln n$ .

Idea

The integral $\int_k^{k+1} \frac{dt}{t}$ lies between $\frac{1}{k+1}$ and $\frac{1}{k}$ . So the gap $H_n - \ln n$ loses a little at each step, but it never drops below $0$ . A decreasing sequence that is bounded below converges. Since the gap stays bounded while $\ln n \to \infty$ , the two sequences are asymptotically equal.

Reading path

To understand this page from the ground up, read these 316 pages in order. The foundations come first. The path takes the proofs Proof that Darboux and Riemann integrals agree, Proof of the Cauchy–Hadamard theorem, Proof that a function with nonnegative second derivative is convex, Proof of the Weierstrass M-test, Proof of the limit of a sum of sequences, Proof of Rolle's theorem, Proof of the approximation property of the supremum, Proof that every sequence has a monotone subsequence, by peaks, Proof of the formula for the derivative of a polynomial, Proof of the reciprocal rule, Proof of the commutativity of addition by induction, Proof of term-by-term differentiation, Proof of the integral of a power, Proof of the epsilon-delta form of continuity, Proof of the power rule by induction, Proof that absolutely convergent series converge, Proof of the sum of a finite geometric series, Proof that convergent sequences are Cauchy, Proof that there is a natural number n with 1/n below any positive epsilon, Proof of the chain rule with an auxiliary difference quotient, Proof of the Cauchy criterion for series, Proof of the Cauchy criterion for sequences by the Bolzano–Weierstrass theorem, Proof of the reverse triangle inequality, Proof that the exponential series has infinite radius of convergence, Proof of the limit of a quotient of sequences, Proof that continuous functions on a closed bounded interval are uniformly continuous, Proof that a function with nonnegative derivative is increasing, Proof that the reals form an ordered field, with the Cauchy sequence construction, Proof of the root test, Proof of the double negation law by a truth table, Proof that the logarithm is the inverse of the exponential, Proof that power series converge uniformly on smaller intervals inside the radius of convergence, Proof of the extreme value theorem by the Bolzano–Weierstrass theorem, Proof of the derivative of the logarithm by the inverse function rule, Proof that the exponential function is positive, Proof of the uniqueness of limits, Proof of the logarithm of a quotient, Proof of strong induction from ordinary induction, Proof that power series are differentiable inside the radius of convergence, Proof of the limit of a product of sequences, Proof that uniform convergence of derivatives allows term-by-term differentiation, Proof that the absolute value is multiplicative, Proof of the squeeze theorem for sequences, Proof of Pascal's rule from the recursive definition, Proof that a differentiable function is convex iff its derivative is increasing, Proof of the linearity of differentiation, Proof that a quotient of continuous functions is continuous, Proof of Riemann's criterion for integrability, Proof of the sequential characterization of limits, Proof that the exponential function is strictly increasing, Proof that Cauchy sequences are bounded, Proof of the triangle inequality for real numbers, Proof of the epsilon-N definition of the limit of a sequence, Proof of the comparison test, Proof of the existence of the infimum by negation, Proof of the continuity of the inverse of a strictly monotone continuous function, Proof of Fermat's theorem on stationary points, Proof that limits preserve non-strict inequalities, Proof that 1 + x is at most exp x, Proof of the linearity of the integral, Proof of the factorial formula for binomial coefficients by induction, Proof that a function with positive derivative is strictly increasing, Proof of the second fundamental theorem of calculus, Proof of the intermediate value theorem by the supremum, Proof of the binomial theorem by induction, Proof that exponentials dominate powers in sequences, by the ratio of consecutive terms, Proof that differentiable functions are continuous, Proof that one-sided limits of a monotone function exist, Proof of the epsilon-delta form of the limit of a function, Proof of the well-ordering principle from strong induction, Proof of the Bolzano–Weierstrass theorem by a monotone subsequence, Proof of the Archimedean property in an Archimedean ordered field, Proof that a composition of continuous functions is continuous, Proof of the exponential of a sum by the Cauchy product, Proof that a decreasing sequence bounded below converges, Proof of the term test, Proof that the exponential function is its own derivative, by term-by-term differentiation, Proof that the reals are Archimedean from the completeness axiom, Proof of the ratio test, Proof that convergent sequences are bounded, Proof of the product rule, Proof of the monotone convergence theorem for sequences, Proof that continuity is equivalent to sequential continuity, Proof of the monotonicity of the integral, Proof of the boundedness theorem by Bolzano–Weierstrass, Proof of the ratio formula for the radius of convergence, Proof that a series of nonnegative terms converges iff its partial sums are bounded, Proof of the mean value theorem from Rolle's theorem, Proof of the logarithm of a product, Proof of the integral of 1/x, Proof that the Cauchy product of absolutely convergent series converges absolutely to the product, Proof that slopes of a convex function are increasing, Proof that continuous functions are Riemann integrable, Proof that the exponential function is strictly convex, Proof of the constant multiple rule.

Big O notation definition
Binomial coefficient definition
Construction of the reals from Cauchy sequences concept
Convex function definition
Definition by recursion concept
Element definition
Factorial definition
Group concept
Harmonic number definition
Integers object
Limit point of a set definition
Local maximum definition
Mathematical induction concept
Natural numbers object
Ordered field definition
Partition of an interval definition
Peano axioms concept
Proposition concept
Rational numbers object
Real numbers object
Sequence definition
Set bounded above definition
Strictly monotone function definition
Little o notation definition
Proof of Pascal's rule from the recursive definition proof
Proof that slopes of a convex function are increasing proof
Strictly convex function definition
Set definition
Ring definition
Ring of integers statement
Limit of a function definition
Local minimum definition
Archimedean ordered field definition
Successor function definition
Mesh of a partition definition
Refinement of a partition definition
Riemann sum definition
Conjunction definition
Disjunction definition
Implication definition
Negation definition
Predicate definition
The reals form a field statement
Real sequence definition
Subsequence definition
Infimum definition
Supremum definition
Asymptotic equivalence definition
Pascal's rule statement
Slopes of a convex function are increasing statement
Ordered pair definition
Commutative ring definition
Continuity at a point definition
Derivative definition
One-sided limit definition
Addition of natural numbers definition
Proof of the Archimedean property in an Archimedean ordered field proof
Riemann integrable function definition
The rationals form a field statement
The successor function is injective statement
Zero is not a successor statement
Biconditional definition
Truth table concept
Modus ponens concept
Existential quantifier definition
Universal quantifier definition
Bounded sequence definition
Cauchy sequence definition
Geometric sequence definition
Limit of a sequence definition
Monotone sequence definition
Sequence tending to infinity definition
Series definition
Completeness axiom statement
Proof of the factorial formula for binomial coefficients by induction proof
Cartesian product definition
Continuous function definition
Differentiable function definition
One-sided derivative definition
Archimedean property statement
Proof of the commutativity of addition by induction proof
Riemann integral definition
Order on the natural numbers definition
Subset definition
The rationals form an ordered field statement
Propositional logic concept
Mathematical proof concept
Upper and lower Darboux sums definition
Uniqueness quantifier definition
Limit superior definition
Proof of the sum of a finite geometric series proof
Convergent sequence definition
Pointwise convergence definition
Sequential continuity definition
The sequence r^n tends to infinity for r > 1 example
Cauchy product definition
Partial sum definition
Power series definition
Factorial formula for binomial coefficients statement
Proof that a composition of continuous functions is continuous proof
Derivative function definition
Binary relation definition
Order on the reals definition
Definite integral definition
Commutativity of addition statement
Proof of strong induction from ordinary induction proof
Tautology definition
Upper and lower Darboux integrals definition
Uniform convergence definition
Sum of a finite geometric series statement
Radius of convergence definition
Convergent series definition
Proof of the binomial theorem by induction proof
Higher derivative definition
Antisymmetric relation definition
Reflexive relation definition
Transitive relation definition
Interval definition
Function definition
Strong induction statement
Uniform convergence on a set definition
Logical equivalence definition
Sum of a series definition
Series of functions definition
Absolute convergence definition
Binomial theorem statement
Second derivative definition
Preorder definition
Proof of the epsilon-delta form of continuity proof
Proof of the epsilon-delta form of the limit of a function proof
Proof of the well-ordering principle from strong induction proof
Proof of the double negation law by a truth table proof
Partial order definition
Epsilon-delta definition of continuity statement
Monotone function definition
Epsilon-delta definition of a limit statement
Well-ordering principle statement
Double negation law statement
Total order definition
Uniform continuity definition
Composition of continuous functions is continuous statement
Proof by contradiction concept
Proof that every sequence has a monotone subsequence, by peaks proof
Uniform continuity on a set definition
Proof that the reals form an ordered field, with the Cauchy sequence construction proof
Every sequence has a monotone subsequence statement
The reals form an ordered field statement
Absolute value definition
Proof of the approximation property of the supremum proof
Proof of the existence of the infimum by negation proof
Proof of the triangle inequality for real numbers proof
Proof that the absolute value is multiplicative proof
Proof of the epsilon-N definition of the limit of a sequence proof
Approximation property of the supremum statement
Existence of the infimum statement
Triangle inequality statement
Absolute value is multiplicative statement
Epsilon-N definition of the limit of a sequence statement
Proof of the intermediate value theorem by the supremum proof
Proof that one-sided limits of a monotone function exist proof
Proof that the reals are Archimedean from the completeness axiom proof
Proof of the reverse triangle inequality proof
Proof of the limit of a sum of sequences proof
Proof of the squeeze theorem for sequences proof
Proof of the uniqueness of limits proof
Proof that limits preserve non-strict inequalities proof
Intermediate value theorem statement
Proof that differentiable functions are continuous proof
Proof of the linearity of the integral proof
Proof that convergent sequences are bounded proof
Proof that convergent sequences are Cauchy proof
The reals are Archimedean statement
The sequence 1/n tends to zero example
Proof that Cauchy sequences are bounded proof
Proof of the term test proof
Proof of the monotone convergence theorem for sequences proof
Reverse triangle inequality statement
Differentiable functions are continuous statement
Proof of the continuity of the inverse of a strictly monotone continuous function proof
Proof that there is a natural number n with 1/n below any positive epsilon proof
Limit of a sum of sequences statement
Linearity of the integral statement
Uniqueness of limits statement
Limits preserve non-strict inequalities statement
Proof of the monotonicity of the integral proof
Convergent sequences are bounded statement
Proof of the ratio formula for the radius of convergence proof
Squeeze theorem statement
Proof that Darboux and Riemann integrals agree proof
Convergent sequences are Cauchy statement
Cauchy sequences are bounded statement
Monotone convergence theorem for sequences statement
Proof of the limit of a product of sequences proof
There is a natural number n with 1/n below any positive epsilon statement
Monotonicity of the integral statement
One-sided limits of a monotone function exist statement
Darboux and Riemann integrals agree statement
Term test statement
Proof that a series of nonnegative terms converges iff its partial sums are bounded proof
Proof that a decreasing sequence bounded below converges proof
The sequence r^n tends to zero for |r| < 1 example
Proof of the sequential characterization of limits proof
Proof that continuity is equivalent to sequential continuity proof
Continuity of the inverse of a strictly monotone continuous function statement
Limit of a product of sequences statement
Decreasing sequence bounded below converges statement
Geometric series example
Proof of Riemann's criterion for integrability proof
A series of nonnegative terms converges iff its partial sums are bounded statement
Proof of the limit of a quotient of sequences proof
Continuity is equivalent to sequential continuity statement
Riemann's criterion for integrability statement
Proof that the Cauchy product of absolutely convergent series converges absolutely to the product proof
Sequential characterization of limits statement
Proof of the root test proof
Proof that exponentials dominate powers in sequences, by the ratio of consecutive terms proof
Proof of the Cauchy–Hadamard theorem proof
Proof of the ratio test proof
Proof of the Bolzano–Weierstrass theorem by a monotone subsequence proof
Proof of the comparison test proof
Proof of the chain rule with an auxiliary difference quotient proof
Proof of the product rule proof
Proof of the linearity of differentiation proof
Limit of a quotient of sequences statement
Comparison test statement
Cauchy product of absolutely convergent series statement
Bolzano–Weierstrass theorem statement
Exponentials dominate powers in sequences statement
Chain rule statement
Product rule statement
Proof of the reciprocal rule proof
Linearity of differentiation statement
Proof that continuous functions on a closed bounded interval are uniformly continuous proof
Proof that a quotient of continuous functions is continuous proof
Ratio test statement
Root test statement
Proof of the boundedness theorem by Bolzano–Weierstrass proof
Proof of the Cauchy criterion for sequences by the Bolzano–Weierstrass theorem proof
Derivative of an inverse function statement
Quotient of continuous functions is continuous statement
Continuous functions on a closed bounded interval are uniformly continuous statement
Proof of the constant multiple rule proof
Reciprocal rule statement
Proof of the power rule by induction proof
Boundedness theorem statement
Ratio formula for the radius of convergence statement
Cauchy–Hadamard theorem statement
Cauchy criterion for sequences statement
Constant multiple rule statement
Power rule statement
Proof of the extreme value theorem by the Bolzano–Weierstrass theorem proof
Uniformly Cauchy sequence of functions definition
Proof of the Cauchy criterion for series proof
Proof of the formula for the derivative of a polynomial proof
Extreme value theorem statement
Proof of Fermat's theorem on stationary points proof
Cauchy criterion for series statement
Derivative of a polynomial statement
Proof that continuous functions are Riemann integrable proof
Proof that absolutely convergent series converge proof
Fermat's theorem on stationary points statement
Continuous functions are Riemann integrable statement
Proof of Rolle's theorem proof
Absolutely convergent series converge statement
Rolle's theorem statement
Proof of the Weierstrass M-test proof
Proof of the mean value theorem from Rolle's theorem proof
Weierstrass M-test statement
Mean value theorem statement
Proof that power series converge uniformly on smaller intervals inside the radius of convergence proof
Proof that a function with nonnegative derivative is increasing proof
Proof that a differentiable function is convex iff its derivative is increasing proof
Proof that uniform convergence of derivatives allows term-by-term differentiation proof
Proof that a function with positive derivative is strictly increasing proof
Power series converge uniformly on smaller discs inside the radius of convergence statement
Proof of the second fundamental theorem of calculus proof
A function with nonnegative derivative is increasing statement
A differentiable function is convex iff its derivative is increasing statement
Uniform convergence of derivatives allows term-by-term differentiation statement
Second fundamental theorem of calculus statement
A function with positive derivative is strictly increasing statement
Proof that the exponential series has infinite radius of convergence proof
Proof that a function with nonnegative second derivative is convex proof
Proof of the integral of a power proof
Proof of term-by-term differentiation proof
The exponential series has infinite radius of convergence statement
A function with nonnegative second derivative is convex statement
Integral of a power statement
Term-by-term differentiation statement
Exponential function definition
Proof of the exponential of a sum by the Cauchy product proof
Proof that power series are differentiable inside the radius of convergence proof
Exponential of a sum statement
Power series are differentiable inside the radius of convergence statement
Proof that the exponential function is positive proof
Proof that the exponential function is its own derivative, by term-by-term differentiation proof
The exponential function is positive statement
The exponential function is its own derivative statement
Proof that the exponential function is strictly increasing proof
The exponential function is strictly increasing statement
Proof that the exponential function is strictly convex proof
Proof that 1 + x is at most exp x proof
Natural logarithm definition
The exponential function is convex statement
1 + x is at most exp x statement
Proof that the logarithm is the inverse of the exponential proof
Logarithm is the inverse of the exponential statement
Proof of the logarithm of a product proof
Proof of the derivative of the logarithm by the inverse function rule proof
Logarithm of a product statement
Derivative of the logarithm statement
Proof of the logarithm of a quotient proof
Logarithm of a quotient statement
Proof of the integral of 1/x proof
Integral of 1/x statement
Proof that harmonic numbers grow like log n proof

Where this leads

6 pages build on this one.

Tag	`QBE5S7KN2B`
URI	`m2://QBE5S7KN2B`
Kind	proof
Writing	W0 stub
MSC	11B83, 26A12
Proves	Harmonic numbers grow like log n
Uses	Harmonic number, Natural logarithm, Integral of 1/x, Logarithm of a quotient, Quotient of continuous functions is continuous, Continuous functions are Riemann integrable, Integral of a power, Linearity of the integral, Monotonicity of the integral, Monotone sequence, Monotone convergence theorem for sequences, Limits preserve non-strict inequalities, Archimedean property, The exponential function is strictly increasing, Little o notation, Asymptotic equivalence
Changed	4 November 2026

Proof that harmonic numbers grow like log n

Proof

Idea

Reading path

Where this leads

Further reading

What this page needs for W1

What links here