# Difference between revisions of "Proof by induction"

(A proof by induction is a technique of mathematical proof) |
|||

(One intermediate revision by the same user not shown) | |||

Line 3: | Line 3: | ||

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

## Revision as of 07:21, 22 August 2008

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

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

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 Axioms, especially the*Induction Axiom*:

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

- zero is an element of the set S

- with any number n, S contains the successor of n

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:

Hypothesis A: *For any Natural Number n, the sum of the numbers less or equal to n is *

- 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 - Show: If A holds for n, then A holds for n+1:
So, we assume that A is true for n:

(*)

We have to show, that then A is true for n+1:

How to do this? For example, the following way, starting with (*):

adding (n+1) on both sides

simplify the right side

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

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