Math

The sum of kth powers

Posted by Dave Richeson on

Everyone loves the “baby Gauss story” in which Gauss amazes his teacher by quickly summing the first 100 positive integers in a flash of brilliance—he adds the first to the 100th, the second to the 99th, and so on to get the sum of fifty 101s to obtain 5050. (Brian Hayes has a great article in which he puts this myth under the microscope). Using this same trick it is easy to show that \displaystyle \sum_{i=1}^{n}i=\frac{n(n+1)}{2}.

Unfortunately, Gauss’ trick doesn’t work for sums of higher powers, \displaystyle\sum_{i=1}^n i^k.

Here is a neat way to compute such sums. (This may be widely known—I haven’t looked for it, but I don’t remember seeing it either.) [Update: OK, I feel silly now—I just looked in Stewart’s Calculus to see how he proves these formulas… and this is the proof he gives. Not a rare gem, I guess, but I still think it is a slick derivation.]

First we’ll derive the formula for \displaystyle \sum_{i=1}^{n}i. We begin with the equality

(i+1)^2=i^2+2i+1, which we rearrange as

2i=(i+1)^2-i^2-1.

Next, sum both sides from 1 to n.

\displaystyle 2\sum_{i=1}^{n}i =\sum_{i=1}^{n}\big((i+1)^2-i^2\big)-\sum_{i=1}^{n}1

The first sum on the right is telescoping and the second is simply n, so

\displaystyle 2\sum_{i=1}^{n}i =((n+1)^2-1)-n=n(n+1).

Dividing by 2 we obtain,

\displaystyle \sum_{i=1}^{n}i=\frac{n(n+1)}{2}.

Now we can repeat this trick to find the sum \displaystyle \sum_{i=1}^{n}i^2.

As before, we begin with an equality.

(i+1)^3=i^3+3i^2+3i+1, or rearranged,
3i^2=(i+1)^3-i^3-1.

Then we sum.

\displaystyle 3\sum_{i=1}^{n}i^2=\sum_{i=1}^{n}\big((i+1)^3-i^3\big)-3\sum_{i=1}^{n}i-\sum_{i=1}^{n}1.

Again, the first sum is telescoping, we just found the second sum, and the third sum is n. So,

\displaystyle 3\sum_{i=1}^{n}i^2=((n+1)^3-1)-\frac{3n(n+1)}{2}-n=\frac{n(n+1)(2n+1)}{2}.

Dividing by 3 we obtain

\displaystyle \sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}.

At this point the pattern is clear. We can find \displaystyle \sum_{i=1}^{n}i^k by expanding (i+1)^{k+1} and using the formulas for \displaystyle \sum_{i=1}^{n}i^m (1\le m<k), which we have already computed.

Further update:
I decided to peruse the calculus books on my shelf and see which of them gave this derivation of the sum of the kth powers. Here’s what I found.
Stewart: yes (and he gives a proof by induction)
Smith/Minton: no (induction)
Larson/Hostetler/Edwards: no (induction)
Edwards/Penney: yes (as a homework problem)
Varberg/Purcell/Rigdon: yes
Hughes-Hallett: the formulas don’t appear in the book as far as I can tell
Rogawski: no (shockingly, he gives these formulas in a definition!)
(Yet another update: Rogawski’s text gives the derivation as a sequence of exercises earlier in the book, it also presents the connections between this problem and the Bernoulli numbers, and according to the author, the “definition” problem will be corrected in the next printing.)