Mathematical Induction

The principle of mathematical induction is based on the fifth Peano Postulate, which states that:

If a statement holds for the positive integer 1, and if, whenever it holds for a positive integer, it also holds for that integer's successor, then the statement holds for all positive integers.

This principle is quite fundamental and is usually taken as a non-provable postulate about the natural numbers. It can be used to prove that a proposition P(n) is true for all n ∈ N. So, the principle of mathematical induction is:

If P(1) is true, and
if the truth of P(r) implies the truth of P(r + 1),
then P(n) is true for all n, n = 1, 2, ....

Of course, one doesn't have to start with 1; one could start with another integer.

As an example, say that we wanted to prove that the n^th triangular number, 1 + 2 + 3 + ... + n is equal to ½n(n + 1), we could:

1. Show that the proposition is true for n = 1. In this case, ½n(n + 1) = 1 when n = 1, so it is true.
2. Assume that the proposition is true for some natural number r, so
   1 + 2 + 3 + ... + r = ½r(r + 1)
3. Based on the assumption in step 2, deduce that the proposition is true for r + 1. In other words, we want to show that
   1 + 2 + 3 + ... + r + r + 1 = ½(r + 1)(r + 2)
   If we add r + 1 to both sides of the equation in step 2, we get:
   1 + 2 + 3 + ... + r + r + 1 = ½(r)(r + 1) + (r + 1)
   
   Expanding the right hand side and then factoring, we get
   1 + 2 + 3 + ... + r + (r + 1) = ½r² + ½r + r + 1
   1 + 2 + 3 + ... + r + (r + 1) = ½r² + ³/₂r + 1
   1 + 2 + 3 + ... + r + (r + 1) = ½(r² + 3r + 2)
   1 + 2 + 3 + ... + r + (r + 1) = ½(r + 1)(r + 2)
   Q.E.D.

Mathematical induction should not be confused with inductive reasoning, which is something different.

Sources used (see bibliography page for titles corresponding to numbers): 20, 51.