[Math Lair] Mathematical Induction

Math Lair Home > Topics > 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 nN. 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 nth 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² + 3/2r + 1
    1 + 2 + 3 + ... + r + (r + 1) = ½(r² + 3r + 2)
    1 + 2 + 3 + ... + r + (r + 1) = ½(r + 1)(r + 2)
    Q.E.D.
Since both parts of the induction principle have been verified, the relation holds for all of the natural numbers.

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.