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.
The 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
Tiny worked example
- Claim: `2^n ≥ n+1` for `n≥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 this kind of problem
- 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.