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

Let $V$ be the space of all polynomials $f:{\mathbb{N}}_{\ge <!--\; \ge \; -->0}\to <!--\; \to \; -->F$ (where $F$ is a field of characteristic zero). Define the forward difference operator $\mathrm{\Delta <!--\; \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 <!--\; \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 $\mathrm{\Delta <!--\; \Delta \; -->}$ as a discrete analogue of the derivative, so it is natural to define the corresponding discrete analogue of the integral $(\int <!--\; \int \; -->f)(n)=\underset{k=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}f(k)$. But of course we need to prove that this actually sends polynomials to polynomials. Since $(\int <!--\; \int \; -->\mathrm{\Delta <!--\; \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 <!--\; \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 $\mathrm{\Delta <!--\; \Delta \; -->}$ is upper triangular in the standard basis, work by induction, or use the Newton basis $1,n,(\genfrac{}{}{0ex}{}{n}{2}),(\genfrac{}{}{0ex}{}{n}{3}),...$ for the space of polynomials. In this basis we have $\mathrm{\Delta <!--\; \Delta \; -->}(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n}{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 <!--\; \sum \; -->n^m$ for fixed $m$. In fact, for any polynomial $f(n)$ we have the "discrete Taylor formula"
$$f(n)=\underset{k\ge <!--\; \ge \; -->0}{\sum <!--\; \sum \; -->}{\mathrm{\Delta <!--\; \Delta \; -->}}^{k}f(0)(\genfrac{}{}{0ex}{}{n}{k})$$
and it's easy to compute the numbers ${\mathrm{\Delta <!--\; \Delta \; -->}}^{k}f(0)$ using a finite difference table and then to replace $(\genfrac{}{}{0ex}{}{n}{k})$ by $(\genfrac{}{}{0ex}{}{n}{k+1})$. 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 ${\displaystyle f(x)=x^m}$ we have
$$\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}f(k)={\int <!--\; \int \; -->}_0^{n}f(x)\text{d}x+\frac{n^m}{2}+\underset{j=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\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
$$\underset{j=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{B_{2j}}{(2j)!}(f^{(2j-<!--\; -\; -->1)}(n)-<!--\; -\; -->f^{(2j-<!--\; -\; -->1)}(0))$$
all are zero after a point ${\displaystyle 2j-<!--\; -\; -->1><!--\; >\; -->m}$ and thus we get the formula for
as a polynomial in ${\displaystyle n}$, with degree $m+1$.