Mathematical induction

Many times we want to establish a proposition or formula $P(n)$ for all $n \in \mbox{${\Bbb Z}$ }^+$. A way to do so is
to establish $P(1)$ and assume that for $m \in \mbox{${\Bbb Z}$ }^+$ that either
(a) $P(m)$ is true OR
(b) $P(k)$ is true for all positive integers $k \le m$,
and on this basis establish the truth of $P(m+1)$. In case (a) the argument is known as the principle of mathematical induction and in case (b), as the principle of complete mathematical induction. Mathematical induction and complete mathematical induction are entirely equivalent. One uses the form most convenient for problem at hand. Examples of formulae that can be so proven are: For each $n \in \mbox{${\Bbb Z}$ }^+$, (the sum of the first $n$ positive integers)

\begin{displaymath}1 + 2 + ... \ + n = \frac{n(n+1)}{2} \end{displaymath}

and (the sum of the squares of the first $n$ positive integers)

\begin{displaymath}1^2 + 2^2 + ... \ + n^2 = \frac{n(n+1)(2n+1)}{6} .\end{displaymath}

There are almost always alternate ways to prove results that can be obtained by an induction argument. For the first formula, one can group and then add the terms as follows the first and last, the second and next to the last, the third and the one next to the one next to the last, etc... We obtain this way

\begin{displaymath}1 + 2 + ... \ + n = [1 + n] + [2 + (n-1)] + [3 + (n-2)] + \ ... \ .\end{displaymath}

Observe that we are now adding $\frac{n}{2}$ terms; each term equals $n+1$. Thus the sum is $\frac{n}{2} (n+1)$. (Why don't we have a problem for $n$ odd?) To prove the second formula by induction, we note that it certainly is valid for $n = 1$ (substitution into both sides). Assuming the formula for $n = m \ge 1$ tells us that

\begin{displaymath}1^2 + 2^2 + ... \ + m^2 = \frac{m(m+1)(2m+1)}{6} .\end{displaymath}

We use this to go to the next step

\begin{displaymath}1^2 + 2^2 + ... \ + m^2 +(m+1)^2 = \frac{m(m+1)(2m+1)}{6} + (m+1)^2 = (m+1) \left ( \frac{m(2m+1)}{6} + (m+1) \right ) \end{displaymath}


\begin{displaymath}= (m+1) \frac{m(2m+1) + 6(m+1)}{6} = (m+1) \frac{2 m^2 + 7 m + 6}{6} = \frac{(m+1)(m+2)(2m+3)}{6} ;\end{displaymath}

the correct formula for $n = m+1$. Can you deduce and then prove the formula for the sum of the cubes of the first $n$ positive integers

\begin{displaymath}1^3 + 2^3 + ... \ + n^3 ?\end{displaymath}

If you are interested in more information concerning mathematical proofs, you might want to consult

1. G.R. Exener, An Accompaniment to Higher Mathematics, Springer, 1996.

or

2. Appendices A and B to: A. Mattuck, An Introduction to Analysis, Prentice Hall, 1999.