# Why is ∑_(k=1)^n k^m a polynomial with degree m+1 in n?

Why is $\sum _{k=1}^{n}{k}^{m}$ a polynomial with degree $m+1$ in $n$?
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Solomon Fernandez
Let $V$ be the space of all polynomials $f:{\mathbb{N}}_{\ge 0}\to F$ (where $F$ is a field of characteristic zero). Define the forward difference operator $\mathrm{\Delta }f\left(n\right)=f\left(n+1\right)-f\left(n\right)$. 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 $\mathrm{dim}{V}_{d}=d+1$.
We want to think of $\mathrm{\Delta }$ as a discrete analogue of the derivative, so it is natural to define the corresponding discrete analogue of the integral $\left(\int f\right)\left(n\right)=\sum _{k=0}^{n-1}f\left(k\right)$. But of course we need to prove that this actually sends polynomials to polynomials. Since $\left(\int \mathrm{\Delta }f\right)\left(n\right)=f\left(n\right)-f\left(0\right)$ (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\left(0\right)=0$, so the forward difference and integral define an isomorphism between ${V}_{d-1}$ and this subspace.
More explicitly, you can observe that $\mathrm{\Delta }$ is upper triangular in the standard basis, work by induction, or use the Newton basis $1,n,\left(\genfrac{}{}{0}{}{n}{2}\right),\left(\genfrac{}{}{0}{}{n}{3}\right),...$ for the space of polynomials. In this basis we have $\mathrm{\Delta }\left(\genfrac{}{}{0}{}{n}{k}\right)=\left(\genfrac{}{}{0}{}{n}{k-1}\right)$, 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\left(n\right)$ we have the "discrete Taylor formula"
$f\left(n\right)=\sum _{k\ge 0}{\mathrm{\Delta }}^{k}f\left(0\right)\left(\genfrac{}{}{0}{}{n}{k}\right)$
and it's easy to compute the numbers ${\mathrm{\Delta }}^{k}f\left(0\right)$ using a finite difference table and then to replace $\left(\genfrac{}{}{0}{}{n}{k}\right)$ by $\left(\genfrac{}{}{0}{}{n}{k+1}\right)$. I wrote a blog post that explains this, but it's getting harder to find.
###### Did you like this example?
Thordiswl
The formula just drops right out if we use the Euler Maclaurin Summation Formula.
For $f\left(x\right)={x}^{m}$ we have

Where ${B}_{j}$ are the Bernoulli numbers and ${f}^{\left(j\right)}\left(x\right)$ is the ${j}^{th}$ derivative of $f$.
Since $f\left(x\right)$ is polynomial, the terms in
$\sum _{j=0}^{\mathrm{\infty }}\frac{{B}_{2j}}{\left(2j\right)!}\left({f}^{\left(2j-1\right)}\left(n\right)-{f}^{\left(2j-1\right)}\left(0\right)\right)$
all are zero after a point $2j-1>m$ and thus we get the formula for
as a polynomial in $n$, with degree $m+1$.