$\sum\limits_{k=1}^nk^r = \frac{1}{1+r}n^{r+1}+a_rn^r +....+a_1n$ 
Show that for every $r \in \mathbb{N}$ there are numbers $a_1,..,a_r \in \mathbb{Q}$ such that $\sum\limits_{k=1}^nk^r = \frac{1}{1+r}n^{r+1}+a_rn^r +....+a_1n$
for all $n \in \mathbb{N}$

There is a hint that I should use the binomial theorem, but I don't know where to use it, and also whether I should use induction.
 A: Given $$\sum\limits_{k=1}^nk^r = \frac{1}{1+r}n^{r+1}+a_rn^r +....+a_1n$$ We need to show, 
$$\sum\limits_{k=1}^{n+1}k^r = \frac{1}{1+r}(n+1)^{r+1}+a_r(n+1)^r +....+a_1(n+1)$$
$$\sum\limits_{k=1}^{n+1}k^r =\sum\limits_{k=1}^nk^r +(n+1)^r = \frac{1}{1+r}n^{r+1}+a_rn^r+....+a_1n + (n+1)^r$$
$$ = \frac{1}{1+r}(n+1-1)^{r+1}+a_r(n+1-1)^r+....+a_1(n+1-1) + (n+1)^r$$
Note that  the binomial theorem implies $$(n+1-1)^b =(n+1)^b +b(n+1)^{b-1}(-1)+...(-1)^b$$
Upon expanding the terms of $$ = \frac{1}{1+r}(n+1-1)^{r+1}+a_r(n+1-1)^r+....+a_1(n+1-1) + (n+1)^r$$
in powers of (n+1) and noticing that the new coefficients are all rational numbers we get the result.
A: We give a proof by induction over $r$.
The case $r=0$ is easy.  Define $$P(i,n) = \sum_{k=1}^n k^i$$ and assume, inductively, that $P(i,n)$ is a polynomial in $n$ of degree $i+1$ with rational coefficients for all $i$ with $0 \le i \le r-1$.  We want to show that $P(r,n)$ is a polynomial of degree $r+1$ with rational coefficients, and that the coefficient of $n^{r+1}$ in this polynomial is $1/(r+1)$.
Consider the sum $\sum_{k=1}^n [(k+1)^{r+1} - k^{r+1} ]$, which telescopes, so
$$\sum_{k=1}^n [(k+1)^{r+1} - k^{r+1}] = (n+1)^{r+1} -1 $$
By the Binomial Theorem,
$$\begin{align}
\sum_{k=1}^n [(k+1)^{r+1} - k^{r+1}] &= \sum_{k=1}^n \left[ \sum_{i=0}^{r+1} \binom{r+1}{i} k^i - k^{r+1} \right]  \\
&= \sum_{k=1}^n  \sum_{i=0}^{r} \binom{r+1}{i} k^i \\
&= \sum_{i=0}^r  \binom{r+1}{i} \sum_{k=1}^{n}  k^i \\
&= \sum_{i=0}^r  \binom{r+1}{i} P(i,n) \\
&= \sum_{i=0}^{r-1}  \binom{r+1}{i} P(i,n) + \binom{r+1}{r} \;P(r,n)\\
(n+1)^{r+1} -1 &= \sum_{i=0}^{r-1}  \binom{r+1}{i} P(i,n) + (r+1) \;P(r,n) \\
\end{align}$$
Therefore
$$P(r,n) = \frac{1}{r+1}\left( (n+1)^{r+1} -1 - \sum_{i=0}^{r-1}  \binom{r+1}{i} P(i,n) \right)$$
The coefficient of $n^{r+1}$ in $(n+1)^{r+1}$ is $1$, and by the inductive hypothesis $P(i,n)$ has degree at most $r$ for $i \le r-1$, so $P(r,n)$ is a polynomial in $n$ of degree $r+1$ with rational coefficients, and the coefficient of $n^{r+1}$ is $1/(r+1)$, as desired.
Note that the final equation can be used to find the formula for the sum $1^r+2^r+3^r+\dots+n^r$, recursively, for a given value of $r$.
