Mathematical Induction

The Principle of Mathematical Induction

Below is a formal definition for mathematical induction:

Let S(1), S(2), ..., S(n), ... be a list of statements, one for each positive integer. Then every statement on the list is true if teh following conditions hold:
(i) S(1) is a true statement,
(ii) For each positive integer k, if S(k) is true, then S(k + 1) is true.

This principle can be used as a proof technique where one is attempting to prove that each statement in an infinite list of statements is true.

This is done by first proving (i) is true, i.e. S(1) is true. The second statement (ii) says that if S(1) is true, then S(2) must also be true. And then using (ii) again, since S(2) is true, S(3) must be true. By application of (ii) an infinite number of times, we show that S(n) is true for all n.

For example, frequently in mathematics a formula wil lbe discover that appears to fit a pattern:
1 = 1²
4 = 2² = 1 + 3
9 = 3² = 1 + 3 + 5
16 = 4² = 1 + 3 + 5 + 7
etc.
From this pattern it appears that 1 + 3 + 5 + 7 + ... + (2n - 1) = n²

We've just proved that this formula works for values of n up to 4. This formula should work for any value of n, but we need to prove it first.

The first step in a proof that uses mathematical induction is to prove that (i) S(1) is true. This step is called the basis step. Obviously from above, 1 = (2(1) - 1) = (2 - 1) = 1.

The next step is called the inductive step. From here we suppose that S(k) is true and prove that S(k + 1) is true. Thus, we must show that

1 + ... + (2(n + 1)) - 1) = (n + 1)²

since S(k) is true,

1 + ... + (2n - 1) = n²

Hence,
1 + ... + (2n - 1) + (2(n + 1) - 1)
= n² + (2(n + 1) - 1)
= n² + 2n + 2 - 1
= n² + 2n + 1
= (n + 1)²

Therefore, S(n + 1) is true.
The inductive proof is now complete.
Most inductive proofs follow this same method of manipulating S(k) to produce S(k + 1). To view another example of an inductive proof, click here.

---