How can we prove the sum of squares/cubes/etc is always a polynomial of appropriate degree? 
What elementary proofs are there that
  $$\sum_{k=1}^{n}k^m$$
  is always a degree $m+1$ polynomial?

It is well known that
$$\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}$$
I'm interested in sums like this for $m\in\mathbb{N}$,
$$\sum_{k=1}^{n}k^m$$
If I know the solution is a polynomial of degree $m+1$, one of the ways I can derive this formula is by computing a small number of sums and solving the appropriate system of equations:
\begin{align*}
\sum_{k=1}^{1}k^2=1&=a(1)^3+b(1)^2+c(1)+d \\
5&=a(2)^3+b(2)^2+c(2)+d \\
14&=a(3)^3+b(3)^2+c(3)+d \\
30&=a(4)^3+b(4)^2+c(4)+d \\
\end{align*}
Like this I can find that $a=\frac{1}{3}$, $b=\frac{1}{2}$, $c=\frac{1}{6}$, and $d=0$. Hence, 
$$\sum_{k=1}^{n}k^2=\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}=\frac{n(n+1)(2n+1)}{6}$$
In fact, it is evident from integration power law rules that in general, $a=1/(m+1)$ so that the leading term is $n^{m+1}/(m+1)$. Once I have the formula like this, it is fairly trivial to prove it using induction.
The general solution to this problem is known, and Wolfram's MathWorld refers to it as Faulhaber's formula. However, beyond proving this formula, are there simple elementary proofs that show the solution will always be a degree $m+1$ polynomial, justifying that the above strategy will always work?

It is known that for $k=2,3$ $(\sum_{x=1}^{n} x^k) $ is a $k+1$ degree polynominal. 
Assume by induction that the equation is true for all $j<k$. 
Cosider following sum:
$\sum_{x=1}^{n}[(x+1)^{k+1}-x^{k+1}] = 2^{k+1}-1^{k+1} +3^{k+1}-2^{k+1}+\ldots + (n+1)^{k+1}-n^{k+1} = (n+1)^{k+1}-1 $.
In other hand $\sum_{x=1}^{n}[(x+1)^{k+1}-x^{k+1}] = \sum_{x=1}^{n} \sum_{j=0}^{k+1}[{ {k+1}\choose j } x^j -x^{k+1}] = 
\sum_{x=1}^{n} \sum_{j=0}^{k}{ {k+1}\choose j } x^j = 
\sum_{j=0}^{k}{ {k+1}\choose j } \sum_{x=1}^{n} x^j 
$
Hence we have:
$   (n+1)^{k+1}-1=  
\sum_{j=0}^{k}{ {k+1}\choose j } \sum_{x=1}^{n} x^j$
$   (n+1)^{k+1}-1=  { {k+1}\choose k } \sum_{x=1}^{n} x^k +
\sum_{j=0}^{k-1}{ {k+1}\choose j } \sum_{x=1}^{n} x^j$
$   (n+1)^{k+1}-1= (k+1) (\sum_{x=1}^{n} x^k) +
\sum_{j=1}^{k-1}{ {k+1}\choose j } (\sum_{x=1}^{n} x^j) + n$
From these equations, we know from mathematical induction that  $(\sum_{x=1}^{n} x^k) $ will always be a degree k+1 polynominal. 
