Hard

Proving Inequalities by Induction

Simple Explanation

Induction can also prove inequalities, not just equations — the base case and inductive step work the same way, but the inductive step uses the assumed inequality (rather than an equation) together with algebra to derive the next inequality. The base case does not have to start at n=1 — it can start at whatever integer the inequality first becomes true.

Why Do We Need It?

Many important results in analysis and computer science (like comparing the growth rates of different functions) are inequalities, not equations — induction is essential for proving these hold for every n.

Formula

Inequality Proofs by Induction

Assume P(k) [an inequality] holds; use it, plus algebra, to show P(k+1) holds too

To prove an inequality holds for every integer n (from some starting value), verify the base case directly, then use the inductive hypothesis (the inequality at k) to derive the inequality at k+1.

Starting value: — the base case does not have to be n=1 — it can be any integer where the inequality first becomes true

When to use it: Whenever an inequality (rather than an equation) needs to be proved true for every integer in a range.

Worked Example

Prove an inequality using induction, starting from a later base case

Prove that n! > 2ⁿ for all integers n ≥ 4.

Why Does This Work?

Multiplying both sides of a true inequality by the same POSITIVE number always preserves the inequality's direction — this is exactly what justifies going from k! > 2ᵏ to (k+1)·k! > (k+1)·2ᵏ, and the rest is just comparing (k+1) to 2 to finish the chain of inequalities.

Real-Life Example

Comparing the growth rates of two algorithms

A computer scientist wants to prove that one algorithm's running time (proportional to n!) eventually always exceeds another's (proportional to 2ⁿ), for large enough input sizes.

An inequality induction proof, starting from the first input size where it becomes true, rigorously confirms this growth-rate comparison holds forever afterward.

Practice

Verify the base case for "n! > 3ⁿ for n≥7" at n=7: what is 7! ?

Hard

Common mistake

Assuming induction must always start at n=1 — the base case can start at any appropriate integer (like n=4 or n=7 above), as long as the inductive step still correctly carries the truth forward from there.

Quick Review

The base case does not need to be n=1 — start wherever the inequality first becomes true.
Multiplying both sides of a true inequality by a positive number preserves its direction.
Use the inductive hypothesis plus algebra to build up to the inequality at k+1.