4,781
edits
Changes
Jump to navigation
Jump to search
A proof by induction is a technique of mathematical proof
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_number|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).
[[Category:Mathematics]]
=== 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).
[[Category:Mathematics]]