Some classic examples are presented below to illustrate the use of mathematical induction to prove inequalities:
Example 1:
Prove the inequality for all positive integers n.
Proof 1:
Let be the proposition that
.
Basis step:
is true, because
. This completes the basis step.
Inductive step:
We first assume the inductive hypothesis that is true for the positive integer k. That is, the inductive hypothesis
is the statement that
. To complete the inductive step, we need to show that if
is true, then
, which is the statement that
is also true. That is, we need to show that if
, then
. To show that this conditional statement is true for the positive integer k, we first add 1 to both sides of
and then note that
. This tells us that
.
This shows that is true; namely, that
, based on the assumption that
is true. The induction step is complete.
Therefore, because we have completed both the basis step and the inductive step, by the principle of mathematical induction we have shown that is true for all positive integers n. QED.
Example 2:
Prove that for every positive integer n with
. (Note that this inequality is false for
).
Proof 2:
Let be the proposition that
Basis Step:
To prove the inequality for requires that the basis step be
. Note that
is true because
.
Inductive Step:
For the inductive step, we assume that is true for the positive integer k with
. That is, we assume that
with
. We must show that under this hypothesis,
is also also true. That is, we must show that if
for the positive integer
, then
. We have
(by definition of exposition)
which (by the inductive hypothesis)
which because
which equals (by definition of factorial function).
This shows that is true when
is true. This completes the inductive step of the proof.
We have completed the basis step and the inductive step. Hence, by mathematical induction is true for all integers n with
. That is, we have proved that
is true for all integers n with
. QED.
An important inequality for the sum of the reciprocals of a set of positive integers will be proved in the example below:
Example 3:
An inequality for Harmonic Numbers
The harmonic numbers are defined by
.
For instance, . Use mathematical induction to show that
, whenever n is a nonnegative integer.
Proof 3:
To carry out the proof, let be the proposition that
.
Basis Step:
is true because
.
Inductive Step:
The inductive hypothesis is the statement that is true, that is,
, where k is a nonnegative integer. We must show that if
is true, then
, which states that
, is also true. So, assuming the inductive hypothesis, it follows that
(by the definition of harmonic number)
which equals (by the definition of the
harmonic number)
(by the inductive hypothesis)
(because there are
terms each greater than or equal to
)
(canceling a common factor of
in second term), which in turn, equals
.
This establishes the inductive step of the proof.
We have completed the basis step and the inductive step. Thus, by mathematical induction is true for all nonnegative integers. That is, the inequality
for the harmonic number is valid for all non-negative integers n. QED.
Remark:
The inequality established here shows that the harmonic series is a divergent infinite series. This is an important example in the study of infinite series.
More later,
Nalin Pithwa
Reference: Discrete Mathematics and its Applications by Kenneth H. Rosen, Seventh Edition.