AN EXAMPLE FOR THE MATHEMATICAL INDUCTION PROOF TECHNIQUE
_____________________________________________________________________________________________

Prove that for any natural number n, the sum of the first n square integers is given by the
following formulla:

           1 + 4 + 9 + 16 + ... + n^2 = (n)(n+1)(2n+1) / 6                        (*)

Proof:

1. Let S = the set of all natural numbers for which the statement (*) is true. We will show
that in fact S = N (the set of all natural numbers).

2. STEP 1: Show that n = 1 is an element of S.

n = 1  =>  LHS of (*) = 1^2 = 1, and

       =>  RHS of (*) = (1)(2)(3) / 6 = 1.

Since, RHS = LHS when n=1, we can conclude that n=1 is an element of S.

3. STEP 2: Assume that for any natural number k, n = k is an element of S, i.e.,

          1 + 4 + 9 + 16 + ... + k^2 = (k)(k+1)(2k+1) / 6.

4. STEP 3: THE INDUCTIVE STEP

Let n = k + 1. We show that k+1 is an element of S.

n = k+1  => LHS of (*) = [1 + 4 + 9 + 16 + ... + k^2] + (k+1)^2

                       = (k)(k+1)(2k+1)/6 + (k+1)^2

                       = (k+1)[(k)(2k+1)/6 + (k+1)]

                       = (k+1)[(2 k^2 + k + 6k + 6) / 6]

                       = (k+1)[(k+2)(2k + 3) / 6]

                       = RHS of (*) when n=k+1

5. STEP 4: CONCLUSION

We proved that n=1 is an element of S. Then, according to the induction step n=2 is an
element of S, and so on. Hence all natural numbers are in S, and hence S=N as required. QED