Mathematical Induction

If P is a property of natural numbers such that

1. P(0) holds, and
2. for every natural number n: P(n) implies P(n+1),

then P holds for all natural numbers.

Rule (1) is known as the "base case" or "basis case". Rule (2) is known as the "induction step", or "inductive step".

A simple proof is by contradiction. Assume the result does not hold. In this case there is a least natural number, x, where P(x) does not hold. We know x≠0 by rule (1) above, therefore there is an x-1 such that P(x-1) holds. However, by rule (2) P(x-1) implies P(x) which is a contradiction.

References

K. Doets. From Logic to Logic Programming. MIT Press, 1994.