Uses of mathematical induction to prove inequalities

Some classic examples are presented below to illustrate the use of mathematical induction to prove inequalities:

Example 1:

Prove the inequality $n<2^{n}$ for all positive integers n.

Proof 1:

Let $P(n)$ be the proposition that $n<2^{n}$ .

Basis step:

$P(1)$ is true, because $1<2^{1}=2$ . This completes the basis step.

Inductive step:

We first assume the inductive hypothesis that $P(k)$ is true for the positive integer k. That is, the inductive hypothesis $P(k)$ is the statement that $k<2^{k}$ . To complete the inductive step, we need to show that if $P(k)$ is true, then $P(k+1)$ , which is the statement that $k+1<2^{k+1}$ is also true. That is, we need to show that if $k<2^{k}$ , then $k+1<2^{k+1}$ . To show that this conditional statement is true for the positive integer k, we first add 1 to both sides of $k<2^{k}$ and then note that $1\leq 2^{k}$ . This tells us that

$k+1<2^{k}+1 \leq 2^{k} + 2^{k} = 2.2^{k}=2^{k+1}$ .

This shows that $P(k+1)$ is true; namely, that $k+1<2^{k+1}$ , based on the assumption that $P(k)$ 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 $n<2^{n}$ is true for all positive integers n. QED.

Example 2:

Prove that $2^{n}<n!$ for every positive integer n with $n \geq 4$ . (Note that this inequality is false for $n=1, 2, 3$ ).

Proof 2:

Let $P(n)$ be the proposition that $2^{n}<n!$

Basis Step:

To prove the inequality for $n \geq 4$ requires that the basis step be $P(4)$ . Note that $P(4)$ is true because $2^{4} =16<24=4!$ .

Inductive Step:

For the inductive step, we assume that $P(k)$ is true for the positive integer k with $k \geq 4$ . That is, we assume that $2^{k}<k!$ with $k \geq 4$ . We must show that under this hypothesis, $P(k+1)$ is also also true. That is, we must show that if $2^{k}<k!$ for the positive integer $k \geq 4$ , then $2^{k+1}<(k+1)!$ . We have

$2^{k+1}=2.2^{k}$ (by definition of exposition)

which $<2.k!$ (by the inductive hypothesis)

which $<(k+1).k!$ because $2<k+1$

which equals $(k+1)!$ (by definition of factorial function).

This shows that $P(k+1)$ is true when $P(k)$ is true. This completes the inductive step of the proof.

We have completed the basis step and the inductive step. Hence, by mathematical induction $P(k)$ is true for all integers n with $n \geq 4$ . That is, we have proved that $2^{n}<n!$ is true for all integers n with $n \geq 4$ . 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 $H_{j}, 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 nonnegative integer.

Proof 3:

To carry out the proof, let $P(n)$ be the proposition that $H_{2^{n}} \geq 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(1)$ is true, that is, $H_{2^{k}} \geq 1+\frac{k}{2}$ , where k is a nonnegative 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}}$ (by the definition of harmonic number)

which equals $H_{2^{n}}+\frac{1}{2^{k}+1} + \ldots + \frac{1}{2^{k+1}}$ (by the definition of the $2^{k}th$ harmonic number)

$\geq (1+\frac{k}{2})+\frac{1}{2^{k}+1}+\ldots + \frac{1}{2^{k+1}}$ (by the inductive hypothesis)

$\geq (1+\frac{k}{2}) + 2^{k}\frac{1}{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), which in turn, equals $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 nonnegative integers. That is, the inequality $H_{2^{n}} \geq 1 + \frac{n}{2}$ for the harmonic number 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 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.

For the love of Maths: the Queen of all Sciences

Uses of mathematical induction to prove inequalities

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply