Changes

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 proceed in order through all the [[Natural_number|natural numbers]]. Proofs by induction are divided into three categories: 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.

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 proceed in order through all the [[natural number]]s. Proofs by induction are divided into three categories: 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 ===

== Weak Induction ==

Hypothesis A is true for 0. Then assume [[hypothesis]] A is true for the number n. Prove that it must be true for n+1.

Hypothesis A is true for 0. Then assume [[hypothesis]] A is true for the number n. Prove that it must be true for n+1.

=== Strong Induction ===

== Strong Induction ==

Hypothesis A is true for 0. Then assume hypothesis A is true for all the numbers less than n. Prove that it must be true for n.

Hypothesis A is true for 0. Then assume hypothesis A is true for all the numbers less than n. Prove that it must be true for n.

=== Technique of Induction ===

== Technique of Induction ==

Both Weak and Strong Induction are based on the [[Peano's Axioms|Peano Axioms]], especially the ''Induction Axiom'':<blockquote>If a set S of numbers contains zero and the successor of every number in S, then S contains every number. </blockquote>

Both Weak and Strong Induction are based on the [[Peano's Axioms|Peano Axioms]], especially the ''Induction Axiom'':<blockquote>If a set S of numbers contains zero and the successor of every number in S, then S contains every number. </blockquote>

If you want to show that an hypothesis A is true for all [[Natural Numbers]], you look at the set S of all numbers for which the hypothesis is true: you show, that <ol><li>zero is an element of the set S <br>

If you want to show that an hypothesis A is true for all [[Natural Numbers]], you look at the set S of all numbers for which the hypothesis is true: you show, that <ol><li>zero is an element of the set S <br>

<math>1 + 2 + 3 + ... + n + (n+1)= \frac{n(n+1)}{2} + (n+1)\quad|</math>simplify the right side<br>

<math>1 + 2 + 3 + ... + n + (n+1)= \frac{n(n+1)}{2} + (n+1)\quad|</math>simplify the right side<br>

<math>\Leftrightarrow</math><br>

<math>\Leftrightarrow</math><br>

<math>1 + 2 + 3 + ... + n + (n+1)=\frac{n(n+1)}{2} + \frac{2(n+1)}{2}=\frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2}</math><p>

<math>1 + 2 + 3 + ... + n + (n+1)=\frac{n(n+1)}{2} + \frac{2(n+1)}{2}=\frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2}</math>

 

 

Now, we're finished: the hypothesis A holds for all the Natural Numbers.

Now, we're finished: the hypothesis A holds for all the Natural Numbers.

=== Transfinite Induction ===

== 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).

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).