Sums of powers of k: a more elegant method

Last week, I put up a post on deriving a formula for 1^k + 2^k + \dots + n^k for positive integer k, using the method of telescoping sums. Interestingly enough, Tim Gowers, a Fields Medallist, just put up a post outlining a very elegant outline of how to derive these formulas. (See his post here.)

In essence, For a positive integer k, consider the (k+1)-dimensional rectangle consisting of integer points (x_1, \dots, x_{k+1}) with 1 \leq latex x_1, \dots, x_k \leq n, and 1 \leq x_{k+1} \leq n+1. By partitioning the rectangle into k+1 parts depending on which coordinate is the largest (with a particular way for breaking ties), one of the partitions has exactly 1^k + \dots n^k points, while the number of points in the rest of the partitions can be expressed as a linear combination of 1^l + \dots n^l, where 0 \leq l \leq k. Hence, if one has formulas for the lower values of l, one can derive the formula for l = k.

This entry was posted in Random and tagged . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment: Logo

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s