Difference Equations, Sum of nth Powers

Sum of Consecutive Integers

When Gauss (biography) was ten years old, his teacher gave his class an assignment that was sure to keep the kids busy for quite a while. The students were told to add up the numbers from 1 to 100. Gauss grouped the integers into pairs: 1+100, 2+99, 3+98, 4+97, etc, and there were 50 such pairs, giving an answer of 5050. He placed his slate on the teacher's desk, sat back down, and waited for his classmates to finish their laborious calculations. (In some versions of the story, a different arithmetic progression is assigned, but the idea is the same.)

A child prodigy, Gaus had discovered the formula for the sum of the first n integers, namely n×(n+1)/2. He went on to become one of the worlds greatest mathematicians.

You are probably familiar with the formula for the sum of the first n integers, but what about the first n squares, or the first n cubes? Regrouping the terms doesn't seem to help at all. It looks like we're lost at sea, but difference equations are going to come to our rescue.

Sum of nth Powers

At this point I'm going to switch variables, so that the sum of the first x integers is (x2+x)/2. This is consistent with the y(x) notation we have established thus far. In fact, we can write the problem as a difference equation: y′ = x+1. The difference between the sum of the first x+1 integers, and the sum of the first x integers, is x+1. The previous section presents a procedure for solving equations of this type. Sure enough, the solution is (x:2)+x, or (x2+x)/2.

The above can be generalized to nth powers. Let y(x) be the sum of jn, as j runs from 0 to x. Now y′(x) = (x+1)n. This is a first order linear difference equation. Rewrite this using binomial coefficients, add one to the exponents, and convert back to a polynomial. When n = 2, (x+1)2 = 2(x:2)+3(x:1)+(x:0). Shift the exponents, and convert back to a polynomial, giving the third entry in the following table.

y0(x) = x   (adding x ones together)

y1(x) = (x2 + x) / 2   (sum of the first x integers)

y2(x) = (2x3 + 3x2 + x) / 6   (sum of the first x squares)

y3(x) = (x4 + 2x3 + x2) / 4   (sum of cubes)

y4(x) = (6x5 + 15x4 + 10x3 - x) / 30   (sum of fourth powers)

Note that (x+1)n has, as its first binomial coefficient, n!×(x:n), which becomes n!×(x:n+1), which produces the leading term xn+1/(n+1). The sum of nth powers, up to x, is a polynomial whose leading term is xn+1/(n+1). For large values of x, this is a good approximation.

Area Under the Curve

Around 350 B.C., Aristotle (biography) and Archimedes (biography) formalized the method of exhaustion, and practically invented integral calculus, some 2,000 years before Riemann. In particular, they knew that the integral of xn was xn+1/(n+1).

Draw a vertical line at x and consider the area under the curve from 0 to x. Divide it into j thin rectangles, each of width x/j. These rectangles, collectively, consume an area that is x/j times the sum of (kx/j)n, as k runs from 1 to j. Pull (x/j)n out of the sum, and you are left with the sum of kn, which is approximately jn+1/(n+1). Put this all together and the area is xn+1/(n+1).

Of course the Greeks didn't develop a full theory of difference equations, but they knew that the sum of the first j nth powers was approximately jn+1/(n+1). (They used induction on j and the binomial theorem to verify this.) Their integrals, trapping the area between lower and upper sums, were as rigorous as anyone would wish, even by today's standards.