Posted by: Dave Richeson | November 12, 2008

The sum of kth powers

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.)

About these ads

Responses

  1. [...] few months ago I wrote about how to sum a finite number of kth powers. Here Euler presents another way of computing these sums. This is by no means the simplest way of [...]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

Follow

Get every new post delivered to your Inbox.

Join 202 other followers

%d bloggers like this: