The method of mathematical induction is based on something that may be considered one of the axioms for the positive integers: If a set S contains 1, and if, whenever S contains an integer k, S contains the next integer k + 1, then S contains all the positive integers. It can be shown that this is equivalent to the principle that in every non-empty set of positive integers there is a least positive integer.

Example 1. Find and prove by mathematical induction a formula for the sum of the first n cubes, that is, 1³ + 2³ + 3³ + ... + n^3.

Solution: We consider the first few cases:

We observe that 1 = 1², 9 = 3², 36 = 6², and 100 = 10². Thus it appears that the sums are the squares of triangular numbers 1, 3, 6, 10, ... . In Chapter 4 we saw that the triangular numbers are of the form n(n + 1)/2. This suggests that

It is clearly true for n = 1. Now we assume that it is true for n = k:

Can we conclude from this that

We can add (k + 1)³ to both sides of the known expression, obtaining:

Hence the sum when n = k + 1 is [n(n + 1)/2]², with n replaced by k + 1, and the formula is proved for all positive integers n.

Our guessed expression for the sum was a fortunate one!
 
 

Monday April 27, 1998