An inequality for harmonic numbers — RMO Inequalities — Basics

The Harmonic Numbers $H_{j}$ for $j=1,2,3, \ldots$ are defined by $H_{j}=1+\frac{1}{2}+\frac{1}{3} +\ldots + \frac{1}{j}$

For instance, $H_{4}=1+\frac{1}{2}+\frac{1}{3} + \frac{1}{4} = \frac{25}{12}$

Use mathematical induction to show that $H_{2^{n}} \geq 1 + \frac{n}{2}$ whenever n is a non-negative integer.

Solution:

To carry out the proof, let P(n) be the proposition that $H_{2^{n}}=1+\frac{n}{2}$

Basis step:

P(0) is true because $H_{2^{0}}=H_{1}=1 \geq 1 + \frac{0}{2}$

Inductive Step:

The inductive hypothesis is the statement that $P(k)$ is true, that is, $H_{2^{k}} \geq 1 + \frac{k}{2}$

where k is a non-negative integer. We must show that if $P(k)$ is true, then $P(k+1)$, which states that $H_{2^{k+1}} \geq 1 + \frac{k+1}{2}$, is also true. So, assuming the inductive hypothesis, it follows that $H_{2^{k+1}} = 1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{2^{k}} + \frac {1}{2^{k}+1} + \ldots + \frac{1}{2^{k+1}}$…this step follows from the definition of harmonic number $=H_{2^{k}} + \frac{1}{2^{k}+1} + \ldots + \frac{1}{2^{k+1}}$….this step again follows by the definition of $2^{k}$th harmonic number $\geq (1+\frac{k}{2}) + \frac{1}{2^{k}+1} + \ldots + \frac{1}{2^{k+1}}$…this step follows by the inductive hypothesis $\geq (1+ \frac{k}{2}) + 2^{k}. \frac{2}{2^{k+1}}$…because there are $2^{k}$ terms each greater than or equal to $\frac{1}{2^{k+1}}$ $\geq (1+\frac{k}{2})+ \frac{1}{2}$….canceling a common factor of $2^{k}$ in second term $= 1 + \frac{k+1}{2}$

This establishes the inductive step of the proof.

We have completed the basis step and the inductive step. Thus, by mathematical induction $P(n)$ is true for all non-negative integers. That is, the inequality $H_{2^{n}} \geq 1 + \frac{n}{2}$ for the harmonic numbers is valid for all non-negative integers n. QED.

Remark:

The inequality established here shows that the harmonic series $1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n} + \ldots$ is a divergent series. This is an important example in the study of infinite series.

Note:

Google, or through some other literature, find out why harmonic numbers are termed so. You will understand something more beautiful, more deeper !!

Nalin Pithwa.

This site uses Akismet to reduce spam. Learn how your comment data is processed.