Induction Summary

Intro to Proofs · Axiom Academy

SUMMARY Unit Summary: Mathematical Induction How induction reduces an infinite proof to two finite checks — the base case and the inductive step. Two essential parts. Both the base case and the inductive step are required — drop either and the proof is invalid. Assumption is not cheating. The inductive hypothesis assumes P(k) as a stepping stone, never as the conclusion. Recognize the pattern. Induction fits statements about all natural numbers — formulas in n , inequalities, divisibility, and recursive structures. Master the template. Induction proofs follow a predictable shape; learn the skeleton, then fill in the problem-specific algebra. Core Concept What Induction Is A proof technique for statements about every natural number, replacing an infinite task with two finite verifications. Picture an infinite line of dominoes: show the first falls, and show each falling domino knocks down the next. Why it's valid: induction is an axiom of the natural numbers, not circular reasoning. When to use: formulas, inequalities, divisibility, or anything defined for all . Core Concept The Two-Step Process Verify the base case P(n_0) — often n_0 = 1 — then assume the inductive hypothesis P(k) for an arbitrary and use it to prove P(k+1) . The chain then falls forever. When to use: the default ("weak") form for most proofs. Watch out for: you must actually use P(k) to reach P(k+1) . Core Concept Strong vs. Weak Induction

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