Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
This also follows directly from the Euler-Maclaurin formula: en.wikipedia.org/wiki/Euler-Maclaurin_formula. Euler-Maclaurin is probably overkill here, though. –  Mike Spivey Jan 26 '11 at 18:33
    
@Mike: Weird! I just noticed your comment, after I added an answer with Euler-McLaurin! –  Aryabhata Jan 26 '11 at 22:40

9 Answers 9

up vote 28 down vote accepted

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.

share|improve this answer
    
Nice answer! A typo: "But of course we need to prove that this actually sends polynomials to polynomials." –  Rahul Jan 25 '11 at 23:27
    
Whoops; thanks for the correction. –  Qiaochu Yuan Jan 25 '11 at 23:28
3  
an even "softer" proof of the surjectivity of $\Delta$ is given in the notes linked to in my answer: observe that $\Delta$ is a linear map from polynomials of degree at most $d$ to polynomials of degree at most $d-1$ and that in fact, $\Delta$ lowers the degree exactly by one. Thus the kernel of $\Delta$ consists of the degree zero polynomials -- a one-dimensional space. So by the dimension formula, $\Delta$ is surjective! (Of course it is better to give $\Delta$ on the Newton basis, as you have done.) –  Pete L. Clark Jan 26 '11 at 0:16
1  
You write that F is an irrelevant field. A better term would be arbitrary field. They don't mean the same thing. –  KCd Aug 12 '12 at 6:07

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

share|improve this answer

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

share|improve this answer
2  
+1: You already know I like this answer. :) –  Mike Spivey Jan 26 '11 at 22:48

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.

share|improve this answer
    
I just read your note, it is excellent! but there is no 5.4 . Is that you left blank as you want reader to find details or it just missed? –  chenbai Apr 16 '13 at 7:34
    
@chenbai: It just means that the section is not yet written. In general my progress on notes like these is sporadic, so don't hold your breath... –  Pete L. Clark Apr 16 '13 at 14:26

Check Faulhaber's formula

share|improve this answer

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

share|improve this answer
    
The script appears broken here. Too bad, I was interested to read it. –  Eric Auld Apr 12 at 0:50

It also follows from Gosper's most excellent algorithm.

share|improve this answer

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

share|improve this answer

No one here has used induction via summation by parts?

Define $G_m(n) = \sum_{k=1}^n k^m$. We'll show that $G_m(n)$ is a polynomial of degree $m+1$. We know that $G_1$ is a polynomial of degree $2$ with leading coefficient of $1/2$. This is the basis step.

Step 1. For the inductive step, since $G_1(k)-G_1(k-1)=\frac{k(k+1)}{2}-\frac{(k-1)k}{2}=k$, summation by parts states that we can write $G_{m+1}(n)$ as

$$\sum_{k=1}^n [G_{1}(k)-G_1(k-1)] k^m = [G_1(n+1)(n+1)^m - G_1(1)(1)^m] - \sum_{k=1}^n G_1(k)[(k+1)^m-k^m]$$ or if you prefer $$G_{m+1}(n) = \left[\frac{(n+1)(n+2)}{2}(n+1)^m - 1 \right] - \sum_{k=1}^n \frac{k(k+1)}{2}[(k+1)^m-k^m].$$

Step 2. The first two terms are the boundary terms, as in normal integration by parts. Since $G_m(k)$ are polynomials of degree $m+1$ and $G_1$ has a leading coefficient of $1/2$, there are coefficients $a_j$ such that we can write

$$\sum_{k=1}^n G_1(k)[(k+1)^m-k^m] = \frac{1}{2} G_{m+1}(n) + \sum_{j=1}^m a_j G_j(n).$$

Step 3. Substituting and solving for $G_{m+1}(n)$ gives $$\frac{3}{2} G_{m+1}(n)= \left[\frac{(n+1)(n+2)}{2}(n+1)^m - 1\right] - \sum_{j=1}^m a_j G_j(n).$$ Noting the orders of $G_j$, it is clear that $G_{m+1}$ has order $m+2$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.