Number theory, possibly mathematical induction to use

Question

For $n, r \in \mathbb{N}$ denote $S_r(n)$ sum $1^r + 2^r + ... + n^r$. Verify that for all $n, r$ : $$(n+1)^{r+1} -(n+1) = \binom{r+1}{1}S_r(n) + \binom{r+1}{2}S_{r-1}(n)+ \cdots +\binom{r+1}{r}S_1(n) $$ To prove this for r, I fixed n and tried induction on r. However my calculations get messy and I can't find a way to do this. Also I have used Pascal's identity for each binomial which resulted in having $(n+1)^{r+2} - (n+1)$ LHS and $(n+1)^{r+1} -(n+1) $ RHS with some coefficients and constants. I'm asking for a clue. I think this task is related to mathematical induction as it is in the same module.

Answer 1

Use binomial formula;

$$ (k+1)^{r+1}= k^{r+1} + \binom {r+1}{1}k^r+ \binom {r+1}{2}k^{r-1}+...+\binom {r+1}{r}k +1 $$

$$ (k+1)^{r+1}- k^{r+1} = \binom {r+1}{1}k^r+ \binom {r+1}{2}k^{r-1}+...+\binom {r+1}{r}k +1 $$

$$ \sum _{k=1}^n \big [(k+1)^{r+1}- k^{r+1}\big]=\sum _{k=1}^n\bigg[\binom {r+1}{1}k^r+ \binom {r+1}{2}k^{r-1}+...+\binom {r+1}{r}k +1\bigg] $$

The LHS telscopes to $$ (n+1)^{r+1}-1$$ and the RHS gives $$ \binom{r+1}{1}S_r(n) + \binom{r+1}{2}S_{r-1}(n)+ \cdots +\binom{r+1}{r}S_1(n) +n$$ That completes the proof.

Answer 2

I am using your notation $$S_r(n):=\sum_{i=1}^n i^r.$$

First, we have that $$(n+1)^{r+1} -1 = \sum_{m=1}^n\left( (m+1)^{r+1}-m^{r+1}\right)$$ (it is a telescopic sum).

Now we use Newton identity $$(m+1)^{r+1}-m^{r+1}=\sum_{i=0}^{r} \binom{r+1}{i} m^i;$$ adding up all this identities we get $$\sum_{m=1}^n \left( (m+1)^{r+1}-m^{r+1}\right)=\sum_{m=1}^n\sum_{i=0}^{r} \binom{r+1}{i} m^i=\sum_{i=0}^{r} \binom{r+1}{i} \sum_{m=1}^n m^i=\sum_{i=0}^{r} \binom{r+1}{i}S_i(n). $$ But $$\binom{r+1}{i}=\binom{r+1}{r+1-i}$$ and $S_0(n)=n$, so we get the identity

$$(n+1)^{r+1} -(n+1)= \sum_{i=1}^r \binom{r+1}{r-i+1}S_i(n)=\binom{r+1}{1}S_r(n) + \binom{r+1}{2}S_{r-1}(n)+ \cdots +\binom{r+1}{r}S_1(n) $$