Induction / Inequalities
Least You Need to Know: Induction for Inequalities
Induction proves inequalities by checking a base case and then comparing the k+1 expression to something already known from the hypothesis.
Least you need to know
- The induction hypothesis must be used in the correct direction.
- For inequalities, algebra after substitution matters as much as the hypothesis itself.
- You may need an extra simple fact like
k+1 ≥ 2. - A valid induction proof still needs a base case.
Key notation
- P(k) — the inequality at step k
- P(k+1) — the target next step
- ≥ — greater than or equal to
Worked example
- Claim:
2^n ≥ n+1forn≥0. - Assume
2^k ≥ k+1. - Then
2^{k+1}=2·2^k ≥ 2(k+1) ≥ k+2, so the step closes.
Common mistakes
- Students often substitute the hypothesis but forget the extra comparison needed at the end.
- Students often reverse the inequality direction incorrectly.
- Students often treat the hypothesis as if it were equality.
How to recognize it
- After using the hypothesis, compare the result to the exact target.
- Look for a simple fact about k that helps finish the inequality.
- Keep the target
P(k+1)visible while doing algebra.
Next recommended lesson
Continue through this topic with Least You Need to Know: Recurrences and Strong Induction.
Least You Need to Know: Recurrences and Strong InductionRelated lessons
Keep going with nearby lessons in the same topic.