Inequality Proofs by Induction
You'll learn how to prove that one expression stays larger (or smaller) than another for all sufficiently large integers using induction.
The Core Idea
Some inequalities aren't equalities—they claim one side is always bigger than the other once you pass a certain starting point. For example, "2^n > n² for all n ≥ 5" says exponential growth beats quadratic growth eventually. Induction is perfect for proving these claims systematically.
The Structure
Just like summing series or divisibility proofs, inequality proofs follow the three-step induction framework:
-
Base Case: Verify the inequality holds at the starting value (often called n₀). For 2^n > n², check n = 5: is 2⁵ > 5²? Yes, 32 > 25 ✓
-
Inductive Hypothesis: Assume the inequality is true for some arbitrary k ≥ n₀. So assume 2^k > k².
-
Inductive Step: Prove it holds for k+1. You need to show 2^(k+1) > (k+1)².
The Key Technique
Start with what you know (2^k > k²) and transform it toward what you need. For our example:
- 2^(k+1) = 2 · 2^k
- By hypothesis, 2^k > k², so 2^(k+1) > 2k²
- Now show 2k² > (k+1)² when k ≥ 5
- Expanding: 2k² > k² + 2k + 1 simplifies to k² > 2k + 1
- This is true for k ≥ 5 ✓
The inequality "chains together," letting you bridge from the assumption to the conclusion.
Why It Matters
Algorithm analysis constantly compares growth rates. Proving one function dominates another tells you which algorithm scales better as input size grows—critical for choosing efficient solutions.
Key Takeaway: Inequality proofs by induction follow the same base-hypothesis-step pattern, but you manipulate inequalities (preserving the < or > direction) to show each case implies the next, often for all n beyond some threshold.