Number theory, possibly mathematical induction to use 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.
 A: 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) $$
A: 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.
