=== Weak Induction ===
Assume 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 ===
Assume 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 ===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. This is known as the induction axiom. </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><math>0 \in S</math><li>with any number n, S contains the successor of n <br><math> n \in S \Rightarrow (n+1) \in S </math></ol> By the ''Induction Axiom'', S then includes all Natural Numbers, i.e., the hypothesis A hold for all Natural Numbers.A standard example for this kind of reasoning is the following:<br>Hypothesis A: ''For any Natural Number n, the sum of the numbers less or equal to n is <math>\frac{n(n+1)}{2}</math>''<ol><li>Show: A holds for zero, i.e., zero is in S:That's easy: The sum of all natural numbers less or equal to zero '''is''' zero, and this equals <math>\frac{0(0+1)}{2}</math><li>Show: If A holds for n, then A holds for n+1:So, we assume that A is true for n:<br>(*) <math>1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}</math><br>We have to show, that then A is true for n+1:<br><math>1 + 2 + 3 + ... + n + (n+1)= \frac{(n+1)((n+1)+1}{2}</math><br>How to do this? For example, the following way, starting with (*):<br> <math>1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}\quad |</math>adding (n+1) on both sides<br><math>\Leftrightarrow</math><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>\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>Now, we're finished: the hypothesis A hold for all the Natural Numbers.
=== Transfinite Induction ===
