Let $r$ be a natural number.
Show that there exist rational numbers $a_{r1},...,a_{rr}$ such that $$\sum_{k=1}^{n} k^{r} = \frac{1}{r+1}n^{r+1}+a_{rr}n^r+...+a_{r1}n$$ for all natural numbers $n$.
I have attempted to prove this statement via induction. It holds for $0$ or $1$, wherever one wishes to start.
Then in the induction step I get (using the binominal theorem):
$$\sum_{k=1}^{n+1} k^{r} = \sum_{k=1}^{n} k^{r} +(n+1)^r= \frac{1}{r+1}n^{r+1}+a_{rr}n^r+...+a_{r1}n+\sum_{k=0}^{r} \binom{r}{k}n^{k}$$
I cannot get the term $\frac{1}{r+1}(n+1)^{r+1}$. How do I proceed? I have tried index shifts, but they do not seem to help.
Given $r$ there are rational numbers, actually integers, such that $$n^r=a_0\binom{n}{0}+a_1\binom{n}{1}+\cdots +a_r\binom{n}{r}$$ this is because the binomial coefficients are independent polynomials so every polynomial of degree $r$, specifically $n^r$ is a linear combination. Now use the formula $$\binom{r}{r}+\binom{r+1}{r}+\cdots +\binom{n}{r}=\binom{n+1}{r+1}$$