Induction and Inequalities

Induction Can Prove More Than Equalities

Induction is often introduced through identities, but the same logical structure proves inequalities. The base case verifies the first comparison. In the inductive step, one assumes the inequality at an index $n$ and uses it, together with other facts, to establish the comparison at $n+1$. The main extra care is algebraic: an inequality does not allow arbitrary substitutions or rearrangements, and a multiplier’s sign can matter.

The Principle of Mathematical Induction established earlier in this course applies to any statement $P(n)$, including a statement such as $a_n\le b_n$. Strong induction, from the previous tutorial, is available when a step requires more than the immediately preceding case. The examples here mostly use ordinary induction: the hypothesis gives one bound, and the recurrence or algebra provides the rest.

Proof strategy. To prove an inequality for all integers $n\ge m$, state the inequality as $P(n)$. Verify $P(m)$. Then fix an arbitrary $n\ge m$, assume $P(n)$, and derive $P(n+1)$. In the step, show explicitly how the assumed bound and any additional comparison combine to give the target.

For example, if $a_n\le b_n$, multiplying both sides by a positive number preserves the comparison, by the theorem on multiplying a non-strict inequality. Adding the same quantity to both sides also preserves it. But if the quantity being multiplied may be negative, the direction could reverse; if it is zero, strictness could disappear. The inductive step must account for those possibilities rather than treating inequalities like equalities.

A First Exponential Bound

A useful starting point is that powers of $2$ eventually provide a simple lower bound for the index. Here $\mathbb{N}_0$ denotes the nonnegative integers, as in the induction results earlier in this course.

Theorem (An Exponential Lower Bound). For every $n\in\mathbb{N}_0$, $$ 2^n\ge n+1. $$

Proof. Let $P(n)$ be the statement $2^n\ge n+1$. At $n=0$, both sides equal $1$, so $P(0)$ holds. Now fix $n\in\mathbb{N}_0$ and assume $2^n\ge n+1$. Since $2>0$, multiplication by $2$ preserves the inequality, giving

2^{n+1}\ge 2(n+1).

Also, $2(n+1)=2n+2\ge n+2$, because $2n+2-(n+2)=n\ge0$. Therefore $2^{n+1}\ge n+2$, which is $P(n+1)$. By the Principle of Mathematical Induction, $P(n)$ holds for every $n\in\mathbb{N}_0$. $\square$

Notice the two parts of the step. The inductive hypothesis first supplies a bound on $2^n$; multiplying by $2$ transfers that bound to $2^{n+1}$. A second comparison, $2(n+1)\ge n+2$, then reaches the desired expression. Skipping that second comparison would leave the argument short of its target.

Worked Example: A Bound for Powers of Three

We prove that $3^n\ge 2n+1$ for every integer $n\ge1$. This statement gives a different linear lower bound and illustrates how the growth of the power appears in the inductive step.

At $n=1$, $3^1=3$ and $2(1)+1=3$, so the base case holds. Assume now that $n\ge1$ and $3^n\ge2n+1$. Since $3>0$,

3^{n+1}=3\cdot3^n\ge3(2n+1)=6n+3.

The right-hand side is at least the desired bound at $n+1$, because

6n+3-\bigl(2(n+1)+1\bigr) =6n+3-(2n+3) =4n \ge0.

Thus $3^{n+1}\ge2(n+1)+1$. Induction proves the inequality for every $n\ge1$. The calculation verifies the comparison for the full stated range, rather than relying only on an informal claim that the power grows faster.

When the Target Needs a Stronger Step

Some inequalities have an inductive step that does not close immediately. Suppose the proposed bound for $n+1$ is quadratic, while the hypothesis bounds the $n$-th power by a quadratic expression in $n$. After using the hypothesis, one still has to check a separate inequality between the resulting expressions. A good proof identifies precisely where that comparison holds and chooses the starting index accordingly.

Worked Example: Bounding a Square by a Power of Two

We prove that $n^2\le2^n$ for every integer $n\ge4$. At $n=4$, the two sides are equal: $4^2=16=2^4$.

Assume $n\ge4$ and $n^2\le2^n$. Multiplying by $2>0$ gives $2n^2\le2^{n+1}$. We now compare $2n^2$ with the square required at the next index:

$$ 2n^2-(n+1)^2 =2n^2-(n^2+2n+1) =n^2-2n-1 =(n-1)^2-2. $$

Since $n\ge4$, we have $n-1\ge3$, so $(n-1)^2\ge9$. Consequently, $(n-1)^2-2\ge7>0$, and therefore $(n+1)^2\le2n^2$. Combining the comparisons gives

(n+1)^2\le2n^2\le2^{n+1}.

This proves the inductive step. Induction starting at $4$ now yields $n^2\le2^n$ for every integer $n\ge4$. The lower limit matters: this proof uses a comparison that is guaranteed by $n\ge4$, and the statement is not asserted for smaller indices.

This example illustrates a useful habit: do not stop after substituting the inductive hypothesis. The hypothesis gives $2^{n+1}\ge2n^2$, but the target is $(n+1)^2\le2^{n+1}$. The intervening comparison $(n+1)^2\le2n^2$ is essential and must be proved under the step’s assumptions.

Factorial Bounds and the Role of the Base Case

For factorials, the recurrence $(n+1)!=(n+1)n!$ naturally turns an inductive bound for $n!$ into a bound for the next factorial. The factor $n+1$ must be compared with the multiplier required by the target. This is another setting where the inductive step has two distinct inequalities.

Worked Example: A Lower Bound for Factorials

For each integer $n\ge1$, we claim that $n!\ge2^{n-1}$. Recall that $n!$ is the product of the positive integers from $1$ to $n$. At $n=1$, $1!=1=2^0$, so the base case holds.

Let $n\ge1$ and assume $n!\ge2^{n-1}$. Since $n+1\ge2$ and $n!>0$, multiplication gives $(n+1)n!\ge2n!$. Using the hypothesis and again multiplying by the positive number $2$, we obtain

(n+1)! =(n+1)n! \ge2n! \ge2\cdot2^{n-1} =2^n.

This is the required bound at $n+1$, since $2^n=2^{(n+1)-1}$. Induction proves $n!\ge2^{n-1}$ for every integer $n\ge1$. Equality holds at $n=1$ and $n=2$; for $n\ge2$, the factor $n+1$ is at least $3$, so the first comparison in the step is strict. In particular, the bound is strict from $n=3$ onward.

The positivity condition in that calculation is not incidental. To pass from $n+1\ge2$ to $(n+1)n!\ge2n!$, we use $n!>0$. This follows because $n!$ is a product of positive integers. Stating the relevant sign makes the direction of the inequality justified.

Choosing a Useful Inductive Statement

A statement can be true for every index in its range and still be awkward to prove by induction if its form does not provide enough information for the next step. The remedy is sometimes to prove a stronger statement—one that includes the desired bound and has a more workable inductive step. The statement must still be verified at the base case, and the stronger conclusion must genuinely imply the original target.

For instance, to prove a bound on $2^n$, it can help to choose a bound whose expression at $n+1$ is directly comparable with a multiple of the expression at $n$. In the square example, multiplying the inductive hypothesis by $2$ produced $2n^2$, and a separate algebraic comparison showed that this dominates $(n+1)^2$. If such a comparison failed for the chosen starting range, the proof would need a different bound, a different starting index, or another method.

State the range precisely.
Choose the first index where the claim is intended to hold, and check the inequality there.

Assume only the current case.
Fix an allowed $n$ and assume the claimed comparison at $n$, not at $n+1$.

Use the recurrence or algebra.
Express the next quantity using earlier quantities, and preserve inequality direction using the relevant sign conditions.

Check the remaining comparison.
Show explicitly that the expression obtained from the hypothesis is strong enough to reach the target at $n+1$.

Invoke induction on the exact statement.
Once the base case and step are established, conclude the inequality throughout the stated range.

Key takeaway. In an inductive inequality proof, the hypothesis is one link in the argument, not the whole step. Verify the base case, preserve inequality direction, and prove the additional comparison that connects the hypothesis to the target at the next index.

Check Your Understanding

Use the induction strategy and the proofs in this tutorial to answer the following questions.

In the proof that $2^n\ge n+1$, what second comparison is needed after multiplying the inductive hypothesis by $2$?
Why is $n\ge4$ sufficient to show that $2n^2\ge(n+1)^2$ in the square-bound example?
In the factorial example, which positive quantity allows the inequality $n+1\ge2$ to be multiplied without reversing its direction?
What is the difference between assuming the inequality at $n$ and proving it at $n+1$?
Why should an inductive proof state the range of indices for which each algebraic comparison is valid?

What You'll Learn