Proof by induction

A proof by induction is a technique of mathematical proof. It is one of the axioms of Zermelo-Fraenkel set theory, allowing a mathematician to have proofs that count in order through all the natural numbers. Proofs by induction come in three flavors: weak (or classic) induction, strong induction, and transfinite induction. As the names suggest, weak induction proofs require fewer assumptions than strong induction proofs. Sometimes these assumptions are too weak, in which case strong induction is necessary. Transfinite induction involves infinitary mathematics, including the Axiom of Choice. Many mathematicians avoid transfinite induction when possible.

Weak Induction

Assume hypothesis A is true for the number n. Prove that it must be true for n+1.

Strong Induction

Assume hypothesis A is true for all the numbers less than n. Prove that it must be true for n.

Transfinite Induction

Assume hypothesis A is true for a finite number n or an infinite cardinal k. Prove it must be true for n+1 (respectively, k+1).