nsTeam1RO, nsTeam1RW, nsTeam1_talkRO, nsTeam1_talkRW
11,789
edits
Changes
Jump to navigation
Jump to search
mLine 3:
Line 3: − Assume [[hypothesis]] A is true for the number n. Prove that it must be true for n+1.+ − Assume hypothesis A is true for all the numbers less than n. Prove that it must be true for n.+ + + + + + + + + + + + + + + + + + + + + + + + + + + + +
Reverted edits by JasonH (Talk); changed back to last version by DiEb
=== 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.
=== 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.
=== 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>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>
Now, we're finished: the hypothesis A hold for all the Natural Numbers.
=== Transfinite Induction ===
=== Transfinite Induction ===