Proof by induction

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

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.

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

1. zero is an element of the set S
   
2. 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

1. 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
2. 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 holds 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).

See also

• Proof by contradiction
• Proof by contraposition