$\sum\limits_{k=1}^nk^r = \frac{1}{1+r}n^{r+1}+a_rn^r +....+a_1n$

Question

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.

Answer 1

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.

Answer 2

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$.