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.

Practice Problems on Cauchy Schwarz Inequality

Below are some problems that I have culled from Prof. Titu Andreescu’s encyclopaedic literature on mathematics olympiads.

Use Cauchy Schwarz inequality to prove the following:

Problem 1:

Let x, y, z > 0. Prove that

\frac{2}{x+y}+\frac{2}{y+z}+\frac{2}{z+x} \geq \frac{9}{x+y+z}

Problem 2:

Let a, b, x, y, z be positive real numbers. Prove that

\frac{x}{ay+bz}+\frac{y}{az+bx}+\frac{z}{ax+by} \geq \frac{3}{a+b}

Problem 3:

Let a, b, c>0. Prove that

\frac{a^{2}+b^{2}}{a+b}+\frac{b^{2}+c^{2}}{b+c}+\frac{c^{2}+a^{2}}{a+c} \geq a+b+c.

Note: 

Perhaps, applying the Cauchy Schwarz inequality directly may be cumbersome, or even impossible. In that case, use the following equivalent lemma for Cauchy Schwarz Inequality:

Lemma:

If a, b, x, y are real numbers and x, y>0, then the following inequality holds:

\frac{a^{2}}{x}+\frac{b^{2}}{y} \geq \frac{(a+b)^{2}}{x+y}.

(I  have solved the above questions using lemma only!! Yet to check whether a direct application of Cauchy Schwarz inequality will work out 🙂 You can enlighten me on this)

Nalin Pithwa