Gauss, when only a child, found a formula for summing the first 100 natural numbers (or so the story goes…). This formula, and his clever method for justifying it, can be easily generalized to the sum of the first \(n\) naturals. While learning calculus, notably during the study of Riemann sums, one encounters other summation formulas. For example, in approximating the integral of the function \(f(x)=x^2\) from \(0\) to \(100\) one needs the sum of the first 100 squares. For this reason, somewhere in almost every calculus book one will find the following formulas collected: \begin{gather*} \sum_{j=1}^n j = \frac{n(n+1)}{2}\\ \sum_{j=1}^n j^2 = \frac{n(n+1)(2n+1)}{6}\\ \sum_{j=1}^n j^3 = \frac{n^2(n+1)^2}{4}. \end{gather*}

A really industrious author might also include the sum of the fourth powers. Jacob Bernoulli (a truly industrious individual) got excited enough to find formulas for the sums of the first ten powers of the naturals. Actually, Bernoulli went much further. His work on sums of powers lead to the definition of what are now known as Bernoulli numbers and let him calculate \(\sum_{j=1}^{1000}j^{10}\) in about seven minutes — long before the advent of calculators! In [16], Bernoulli is quoted:

With the help of this table it took me less than half of a quarter of an hour to find that the tenth powers of the first 1000 numbers being added together will yield the sum \begin{equation*} 91,409,924,241,424,243,424,241,924,242,500. \end{equation*}

To the beginning calculus student, the beauty of the above relationships may be somewhat dimmed by the memorization challenge that they represent. It is fortunate then, that the right-hand side of the third formula is just the square of the right-hand side of the first formula. And of course, the right-hand side of the first formula is something that can be deduced by a six year old child (provided that he is a super-genius!) This happy coincidence leaves us to apply most of our rote memorization energy to formula number two, because the first and third formulas are related by the following rather bizarre-looking equation, \begin{equation*} \sum_{j=1}^n j^3 = \left( \sum_{j=1}^n j \right)^2. \end{equation*}

The sum of the cubes of the first \(n\) numbers is the square of their sum.

For completeness we should include the following formula which should be thought of as the sum of the zeroth powers of the first \(n\) naturals. \begin{equation*} \sum_{j=1}^n 1 = n \end{equation*}

Our challenge today is not to merely memorize these formulas but to prove their validity. We'll use PMI.

Before we start in on a proof, it's important to figure out where we're trying to go. In proving the formula that Gauss discovered by induction we need to show that the \(k+1\)–th version of the formula holds, assuming that the \(k\)–th version does. Before proceeding on to read the proof do the following

Notice how the inductive step in this proof works. We start by writing down the left-hand side of \(P_{k+1}\), we pull out the last term so we've got the left-hand side of \(P_{k}\) (plus something else), then we apply the inductive hypothesis and do some algebra until we arrive at the right-hand side of \(P_{k+1}\). Overall, we've just transformed the left-hand side of the statement we wish to prove into its right-hand side.

There is another way to organize the inductive steps in proofs like these that works by manipulating entire equalities (rather than just one side or the other of them).

Inductive step (alternate): By the inductive hypothesis, we can write \begin{equation*} \sum_{j=1}^{k} j = \frac{k(k+1)}{2}. \end{equation*} Adding \((k+1)\) to both side of this yields \begin{equation*} \sum_{j=1}^{k+1} j = (k+1) + \frac{k(k+1)}{2}. \end{equation*} Next, we can simplify the right-hand side of this to obtain \begin{equation*} \sum_{j=1}^{k+1} j = \frac{(k+1)(k+2)}{2}. \end{equation*} Q.E.D.

Oftentimes one can save considerable effort in an inductive proof by creatively using the factored form during intermediate steps. On the other hand, sometimes it is easier to just simplify everything completely, and also, completely simplify the expression on the right-hand side of \(P(k+1)\) and then verify that the two things are equal. This is basically just another take on the technique of “working backwards from the conclusion.” Just remember that in writing-up your proof you need to make it look as if you reasoned directly from the premises to the conclusion. We'll illustrate what we've been discussing in this paragraph while proving the formula for the sum of the squares of the first \(n\) positive integers.

Notice how the last four lines of the proof are the same as those in the box above containing our scratch work? (Except in the reverse order.)

We'll end this section by demonstrating one more use of this technique. This time we'll look at a formula for a product rather than a sum.

Before preceding with the proof let's look at an example (although this has nothing to do with proving anything, it's really not a bad idea — it can keep you from wasting a lot of time trying to prove something that isn't actually true!) When \(n = 4\) the product is \begin{equation*} \left(1-\frac{1}{2^2}\right) \cdot \left(1-\frac{1}{3^2}\right) \cdot \left(1-\frac{1}{4^2}\right). \end{equation*}

This simplifies to \begin{equation*} \left( 1-\frac{1}{4} \right) \cdot \left( 1-\frac{1}{9} \right) \cdot \left( 1-\frac{1}{16} \right) = \left( \frac{3}{4} \right) \cdot \left( \frac{8}{9} \right) \cdot \left( \frac{15}{16} \right) = \frac{360}{576}. \end{equation*}

The formula on the right-hand side is \begin{equation*} \frac{4+1}{2 \cdot 4} = \frac{5}{8}. \end{equation*}

Well! These two expressions are clearly not equal to one another… What? You say they are? Just give me a second with my calculator…

Alright then. I guess we can't dodge doing the proof…