Proof by induction
A claim about every whole number is an endless list of claims. How can a finite amount of work prove all of them?
Where you are 3 inside
What this area is about
Proof by induction proves a statement P(n) for every integer n \ge n_0 in two parts. The base case proves P(n_0). The inductive step proves that, for every k \ge n_0, if P(k) holds then P(k+1) holds. Both parts are needed: a step without a base case proves nothing, and checking many cases is not a proof. Together they reach every n \ge n_0, one case after another.
How these fit together
The method. How induction works: base case, hypothesis and step names the three parts, explains why they settle every case, and shows how a proof can go wrong.
A variant. Strong induction and well-ordering lets the step assume P(n_0), \ldots, P(k), every earlier case, to prove P(k+1). It fits when breaking a case apart gives smaller pieces whose sizes are not known in advance. The well-ordering principle runs the same idea as a search for a smallest counterexample.
A standard use, not yet written. Induction on a sum formula will prove a closed formula for a running total by adding one more term to the assumed case. Until it exists, the first lesson’s own section on sum formulas covers this use.
A path through it
How induction works comes first; strong induction builds on it.
Induction is the tool behind trees, where a tree on n vertices has n - 1 edges, and behind checking a closed formula in solving a two-term recurrence.