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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s