Why is ∑_(k=1)^n k^m a polynomial with degree m+1 in n?
Why is a polynomial with degree in ?
Answer & Explanation
Let be the space of all polynomials (where is a field of characteristic zero). Define the forward difference operator . It is not hard to see that the forward difference of a polynomial of degree is a polynomial of degree , hence defines a linear operator where is the space of polynomials of degree at most . Note that .
We want to think of as a discrete analogue of the derivative, so it is natural to define the corresponding discrete analogue of the integral . But of course we need to prove that this actually sends polynomials to polynomials. Since (the "fundamental theorem of discrete calculus"), it suffices to show that the forward difference is surjective as a linear operator .
But by the "fundamental theorem," the image of the integral is precisely the subspace of of polynomials such that , so the forward difference and integral define an isomorphism between and this subspace.
More explicitly, you can observe that is upper triangular in the standard basis, work by induction, or use the Newton basis for the space of polynomials. In this basis we have , and now the result is really obvious.
The method of finite differences provides a fairly clean way to derive a formula for for fixed . In fact, for any polynomial we have the "discrete Taylor formula"
and it's easy to compute the numbers using a finite difference table and then to replace by . I wrote a blog post that explains this, but it's getting harder to find.
The formula just drops right out if we use the Euler Maclaurin Summation Formula.
For we have
Where are the Bernoulli numbers and is the derivative of .
Since is polynomial, the terms in
all are zero after a point and thus we get the formula for
as a polynomial in , with degree .