why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$

Question

why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$?

I know this is well-known. But how to prove it rigorously? Even mathematical induction does not seem so straight-forward.

Thanks.

Answer 1

Let $V$ be the space of all polynomials $f : \mathbb{N}_{\ge 0} \to F$ (where $F$ is an irrelevant field). Define the forward difference operator $\Delta f(n) = f(n+1) - f(n)$. It is not hard to see that the forward difference of a polynomial of degree $d$ is a polynomial of degree $d-1$, hence defines a linear operator $V_d \to V_{d-1}$ where $V_d$ is the space of polynomials of degree at most $d$. Note that $\dim V_d = d+1$.

We want to think of $\Delta$ as a discrete analogue of the derivative, so it is natural to define the corresponding discrete analogue of the integral $(\int f)(n) = \sum_{k=0}^{n-1} f(k)$. But of course we need to prove that this actually sends polynomials to polynomials. Since $(\int \Delta f)(n) = f(n) - f(0)$ (the "fundamental theorem of discrete calculus"), it suffices to show that the forward difference is surjective as a linear operator $V_d \to V_{d-1}$.

But by the "fundamental theorem," the image of the integral is precisely the subspace of $V_d$ of polynomials such that $f(0) = 0$, so the forward difference and integral define an isomorphism between $V_{d-1}$ and this subspace.

More explicitly, you can observe that $\Delta$ is upper triangular in the standard basis, work by induction, or use the Newton basis $1, n, {n \choose 2}, {n \choose 3}, ...$ for the space of polynomials. In this basis we have $\Delta {n \choose k} = {n \choose k-1}$, and now the result is really obvious.

The method of finite differences provides a fairly clean way to derive a formula for $\sum n^m$ for fixed $m$. In fact, for any polynomial $f(n)$ we have the "discrete Taylor formula"

$$f(n) = \sum_{k \ge 0} \Delta^k f(0) {n \choose k}$$

and it's easy to compute the numbers $\Delta^k f(0)$ using a finite difference table and then to replace ${n \choose k}$ by ${n \choose k+1}$. I wrote a blog post that explains this, but it's getting harder to find; I also explained it in my notes on generating functions.

Answer 2

You can set up a recursive formula for $\sum_{k=0}^n k^m $ by noting that

$$(n+1)^{m+1} = \sum_{k=0}^n (k+1)^{m+1}- \sum_{k=0}^n k^{m+1}$$ $$ = { m+1 \choose 1} \sum_{k=0}^n k^m + { m+1 \choose 2} \sum_{k=0}^n k^{m-1} + \cdots $$

by expanding the first summation on the RHS by the binomial theorem. Then shift all the other summations except $\sum_{k=0}^n k^m $ to the LHS.

So we get

$${ m+1 \choose 1} \sum_{k=0}^n k^m = (n+1)^{m+1} - { m+1 \choose 2} \sum_{k=0}^n k^{m-1} - { m+1 \choose 3} \sum_{k=0}^n k^{m-2} + \cdots $$

Answer 3

The formula just drops right out if we use the Euler Maclaurin Summation Formula.

For $\displaystyle f(x) = x^m$ we have

$$ \sum_{k=0}^{n} f(k) = \int_{0}^{n} f(x)\ \text{d}x + \frac{n^m}{2} + \sum_{j=0}^{\infty} \frac{B_{2j}}{(2j)!} (f^{(2j-1)}(n) - f^{(2j-1)}(0))$$

Where $\displaystyle B_j$ are the Bernoulli numbers and $\displaystyle f^{(j)}(x)$ is the $\displaystyle j^{th}$ derivative of $\displaystyle f$.

Since $\displaystyle f(x)$ is polynomial, the terms in

$$ \sum_{j=0}^{\infty} \frac{B_{2j}}{(2j)!} (f^{(2j-1)}(n) - f^{(2j-1)}(0))$$

all are zero after a point ($\displaystyle 2j-1 \gt m$) and thus we get the formula for

$\displaystyle \sum_{k=0}^{m} k^m$ as a polynomial in $\displaystyle n$, with degree $m+1$.

Answer 4

Qiaochu's answer is (as always?) right on the money.

I just wanted to mention that I also wrote up some notes about "discrete calculus" which takes the question of finding a closed form for the sums of $k$th powers as a jumping off point. This came from a sophomore level undergraduate course I taught on introduction to proofs, in which we were doing suspiciously many induction proofs involving such closed forms, and I came to understand belatedly that the students found these confusing. Not because they didn't understand the mechanism of induction (at least, not for the most part), but because they couldn't help but fixate on the nontrivial question: how do you know what closed form expression to put on the right hand side? In the context of their exercises, the answer is: "You know because you are being given this information as part of the problem." But of course that's a stupid answer: really, how do you know?

So I wrote up these notes on the subject of discrete calculus. Or at least I started to: they are not quite complete and are a little more complicated than what I was expecting of the students, so I ended up not giving them out. See especially Section 2, which explores the issue raised in the previous paragraph and also gives the extra little push (an innocuous recursive formula for the power sums) you need in order to prove by induction that $1^k + \ldots + n^k$ is a degree $k+1$ polynomial in $n$. Note also that Qiaochu's nice linear algebra argument comes later, in Section 4 ("Linear Algebra of the Discrete Derivative") and especially Theorem 11.

As usual, any suggestions or corrections on these notes are most welcome, although (as usual) I certainly do not claim that there are few enough typos for it to be worth your time to point them out to me one by one.

Answer 5

Check Faulhaber's formula

Answer 6

Have you seen this (article about sum of powers)? In particular, one uses telescoping to prove the above result.

Answer 7

It also follows from Gosper's most excellent algorithm.

Answer 8

$$ \sum_{k=1}^n k^m = \sum_{i=0}^{m-1} T(m,i) \binom{n+i+1}{m+1}$$ where $T(m,i)$ is an Eulerian number. (OEIS id:A008292)

Since $\binom{n+i+1}{m+1}$ is a polynomial of degree $m+1$ in $n$, so is $ \sum_{k=1}^n k^m $.