## 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$.