Induction, Sums of Powers of Integers, and Patterns

Prepared by:

Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk/

What is the sum of the first n positive integers? It is not difficult to see that this sum, as shown below, is given by a quadratic polynomial in n.

1 + 2 + 3 + 4 + .... + n = n(n+1)/2 (*)

Note that this equation (*) is "shorthand" for infinitely many statements that are being asserted to be true, namely statements for n = 1, n = 2, etc. This is a very helpful result. For example, in Calculus when proving a result for the integral of the function x, going back to the Riemann Sum definition, it becomes necessary to find a formula for the sum of the first n integers. This formula (e.g. (*)) can be proved by mathematical induction or a variety of visual diagrams which serve as "proofs without words." A proof without words is a physical model representation for a mathematical statement which helps show why the statement is true. Actually, words are allowed for proofs without words, and often annotations of the diagrams helps make clear how the proof works. Here (Figure 1) is a proof without words for (*). The diagram illustrates the case n = 3.

Figure 1

For another example, Figure 2 enables one to see that the sum of the first n odd integers is n². For example, for n = 4 we have 1 + 3 + 5 + 7 = 4².

Figure 2

Each "hook" in Figure 2 (illustrating the case n = 8) has an odd number of cells and the union of these hooks is a physical square of cells. The role of the color is to clarify the structure and location of the hooks.

Since we can think of (*) as summing the first power of the integers from 1 to n, are there nice formulas for the sum of the second, third, etc., powers of n?

The answer is that there are certainly formulas, and it is a nice "game" for you and your students to see if they are nice. What patterns can you find in the formulas below, which are shown in factored form, and perhaps you can see other patterns if you multiply out the polynomials shown and look at the polynomials that you get.



This list shows the formulas for the sum of the powers of integers for the cases from 1 to 8. If you are wondering how one could find these formulas, if one picks a particular line one can work out the sum for n - 1, n =2, etc. and now try to find a formula that "fits" the data. This is exactly what promoted Isaac Newton to develop a polynomial formula for "data" where one has values for n = 0, n = 1, n = 2, etc. If one takes the data and computed the differences between consecutive terms one gets "first differences." If one repeatedly does this and gets a table whose rows are differences which terminates with a row of constants, after k rows, then Newton showed there is a polynomial of degree k which fits the data. The coefficients of this polynomial p(x) are p(0), p'(0), p''(0), etc., where pⁱ(0) refers to the ith derivative of p(x) evaluated at 0. Recall that the kth derivative of a polynomial of degree k is a constant. The formula that Newton found is what today we call the Maclaurin or Taylor series for the polynomial.

If you rewrite the third line above you get the very appealing identity:

1³ + 2³ + 3³ + ... + n³ = (1 + 2 + 3 + .... + n )²

A nice challenge is to see if you can find a proof without words for this identity.