Binomial coefficients identity (sum of the powers of the natural numbers)

Question

I've found exercise with binomial coefficients in Kostrikin's book.

Proof that

$\sum_{i=1}^n{{r+1}\choose{i}}\left(1^i+2^i+\dots+n^i\right)=(n+1)^{r+1}-(n+1)$

I was trying to check that for small integers like $r=2$ and $n=1,2$ but i think that there is something wrong. My results didn't match.

For $r=2$ and $n=1$ we have ${{3}\choose{1}}\left(1^1\right)=3\not=2^3-2=6$. For $r=2$ and $n=2$, ${{3}\choose{1}}\left(1^1\right)+{{3}\choose{2}}\left(1^2+2^2\right)=18\not=3^3-3=24$. I can't find this identity anywhere. Is this identity known? How can i proof that without mathematical induction?

Answer 1

As André Nicolas correctly pointed out, the correct version of this identity can be obtained by working backwards from a much simpler one:

$$\sum_{j=1}^n (j+1)^{r+1} - j^{r+1} = (n+1)^{r+1} - 1$$

The sum on the left-hand side has telescopic property; each term cancels out part of the previous one, so in the end, only the very first and very last parts remain.

Now, if we apply binomial theorem to the term $(j+1)^{r+1}$ inside the sum and rearrange the terms a little (changing the order of summation in the last step), we get

$$\begin{eqnarray} (n+1)^{r+1} - 1 & = & \sum_{j=1}^n \left(\left(\sum_{i=0}^{r+1} \binom{r+1}{i} j^i\right) - j^{r+1}\right)\\ & = & \sum_{j=1}^n \left(1+\sum_{i=1}^{r} \binom{r+1}{i} j^i\right) \\ & = & n + \sum_{j=1}^n \sum_{i=1}^{r} \binom{r+1}{i} j^i \\ & = & n + \sum_{i=1}^r \binom{r+1}{i}\sum_{j=1}^n j^i \end{eqnarray} $$

Comparing what we started with and the final sum, it's almost what you wanted to prove -- except for a tiny mistake: the upper bound in the outer summation should have been $r$ instead of $n$:

$$\sum_{i=1}^r \binom{r+1}{i}\sum_{j=1}^n j^i = (n+1)^{r+1} - (n+1)$$

Oh, and as a bonus, we've just proved it :-)