4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.