25
edits
Changes
Jump to navigation
Jump to search
Line 3:
Line 3: − 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 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. − − − − − −
no edit summary
=== Weak Induction ===
=== Weak Induction ===
Assume [[hypothesis]] A is true for the number n. Prove that it must be true for n+1.
=== Strong Induction ===
=== Strong Induction ===
Assume hypothesis A is true for all the numbers less than n. Prove that it must be true for n.
=== Transfinite Induction ===
=== Transfinite Induction ===