Inequality Induction

Intro to Proofs · Axiom Academy

Techniques for proving inequalities by induction — handling strict vs. non-strict, strengthening the hypothesis, and bringing in calculus. To prove an inequality P(n) for all by induction, we keep the standard three-part structure — but with one extra duty: the inductive step must carry the inequality forward , not just an equation. Base case: verify P(n_0) is true. Inductive hypothesis: assume P(k) holds for some . Inductive step: prove P(k + 1) from P(k) , keeping the inequality intact. The claim: the big side stays on top, for every n Step: assume . Then since reduces to . ✓︎ 2. Strict vs. Non-Strict Inequalities The gap between and ) matters in induction. A non-strict claim may sit on the boundary; a strict claim must keep a genuine gap at every step, and that gap is exactly what the inductive step has to defend. Can touch the boundary — equality is allowed at any step, so these are usually easier. Must hold a positive gap — you have to show the difference stays > 0 , never just = 0 . Worked example: prove 2^n > n for all Step: assume 2^k > k . Then using for the last step. ✓︎ The strict > is supplied by the first link, ; the closing only needs (indeed k + k = k+1 at k=1 ), and a strict-then- chain is still strict. 3. The Strengthening Technique Sometimes the direct approach stalls because the hypothesis simply isn't strong enough to feed the next step. The fix is counter-intuitive: prove a stronger statement that carries more information forward.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.