Previous:  Induction and Contradiction

The statement that we wish to prove in this article can be written as follows: 

To see that this is a reasonable proposition, take a simple example, say n = 3.  The sum of the cubes of 1, 2 and 3 is 1 + 8 + 27 = 36.  The sum of the integers 1, 2 and 3 is 6, which gives 36 when squared. 

Let us begin by evaluating the sum of the first n integers.  We assert that 

We will prove that this is correct by using proof by induction.  The two steps of a proof by induction are as follows: 

1.  Demonstrate that the statement to be proved holds for the case n = 0 (or n = 1) 

2.  Demonstrate that if the statement to be proved holds for the case n, then it also holds for the case n + 1. 

Let us consider the first step, and take the case n = 1.  Clearly both sides of the above expression are unity, so the expression holds for n = 1. 

Now let us consider the second step.  We assume that the statement above is true for the case n.  Let us see what happens if we consider the case with n + 1.  This introduces an extra term into our original sum: 

Here the last term on the right-hand side of this expression is simply the extra term that needs to be added to the sum of the first n integers.  Now, elementary algebra shows us that 

Now, if we examine this expression carefully, we see that it is of the form 

with n + 1 instead of n.  This is the result that we seek.  It shows us that if our proposed result holds for the case n, then it also holds for the case n + 1. 

The proof by induction is complete.  We have satisfied both requirements of the proof by induction, and hence we have proved that 

Therefore, proving our original statement requires us to prove that 

Again, this can be proved by induction.  We again use the two steps outlined above. 

For the case n = 1, the statement clearly holds since the sum of cubes and the expression on the right-hand side of the above evaluates to unity.  Now let us consider the statement with the case n + 1.  We get: 

where the last term on the right-hand side of this expression is just the extra term that needs to be added to the sum of the cubes of the first n integers. 

Now a little manipulation shows that 

We can see that the right-hand side of the above expression is of the form 

with n + 1 instead of n.  This is the result that we seek.  It shows us that if our proposed result holds for the case n, then it also holds for the case n + 1. 

The proof by induction is complete.  We have satisfied both requirements of the proof by induction, and hence we have proved that 

as required.

Next:  Infinite Number of Primes