Proving Inequalities by Induction
You'll learn how to use mathematical induction to prove that one expression is always greater than (or less than) another for all integers beyond a certain threshold.
The Core Idea
Sometimes we need to prove that an inequality holds for all sufficiently large values of n. For example, exponential functions eventually outgrow polynomial functions, but this might only be true starting at some specific value. Mathematical induction is perfect for this: once we verify the inequality at a base case, we can show it propagates forward step-by-step.
The Strategy
Base Case: Find the smallest integer n₀ where the inequality first becomes true, then verify it explicitly.
Inductive Step: Assume the inequality holds for n = k (this is your inductive hypothesis). Then prove it must also hold for n = k+1 using algebraic manipulation and the hypothesis.
Example Pattern
To prove 2ⁿ > n² for n ≥ 5:
- Base: Check n = 5: 2⁵ = 32 > 25 = 5². ✓
- Inductive: Assume 2^k > k² for some k ≥ 5.
- Goal: Show 2^(k+1) > (k+1)².
Starting from the left side: 2^(k+1) = 2 · 2^k > 2k² (by hypothesis)
Now we need 2k² ≥ (k+1)² = k² + 2k + 1, which simplifies to k² ≥ 2k + 1. For k ≥ 5, this is clearly true. Done!
Why This Works
Think of it like climbing a ladder that starts partway up a cliff. You verify you can reach the first rung (base case), then prove that standing on any rung lets you reach the next one (inductive step). The inequality might fail for small values—that's fine; we're only claiming it works above our starting point.
Key Takeaway: Proving inequalities by induction requires finding the right base case where the inequality first holds, then carefully manipulating the inductive hypothesis to establish the next step—often requiring additional algebra to bridge the gap.