Upper Bound for Harmonic Number

From ProofWiki
Jump to navigation Jump to search

Theorem

$H_{2^m} \le 1 m$

where $H_{2^m}$ denotes the $2^m$th harmonic number.


Proof

$\ds \sum_{n \mathop = 1}^\infty \frac 1 n = \underbrace 1_{s_0} \underbrace {\frac 1 2 \frac 1 3}_{s_1} \underbrace {\frac 1 4 \frac 1 5 \frac 1 6 \frac 1 7}_{s_2} \cdots$

where $\ds s_k = \sum_{i \mathop = 2^k}^{2^{k 1} \mathop - 1} \frac 1 i$


From Ordering of Reciprocals:

$\forall m, n \in \N_{>0}: m > n: \dfrac 1 m < \dfrac 1 n$

so each of the summands in a given $s_k$ is less than $\dfrac 1 {2^k}$.

The number of summands in a given $s_k$ is $2^{k 1} - 2^k = 2 \times 2^k - 2^k = 2^k$, and so:

$s_k < \dfrac {2^k} {2^k} = 1$


Hence the harmonic sum $H_{2^m}$ satisfies the following inequality:

\(\ds \sum_{n \mathop = 1}^{2^m} \frac 1 n\) \(=\) \(\ds \sum_{k \mathop = 0}^m \paren {s_k}\)
\(\ds \) \(<\) \(\ds \sum_{a \mathop = 0}^m 1\)
\(\ds \) \(=\) \(\ds 1 m\)

Hence the result.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Upper_Bound_for_Harmonic_Number&oldid=629907"