2

Can you give me any hint how to prove that

$\sum_{k=0}^{n-1} (n-k)(k+1) = \frac{n(n+1)(n+2)}{6}$

  • I tried to divide this sum into two cases when $n$ is odd and even but it does not give me any proper result.
  • I can see that the result on the right side is the same as $\binom{n+2}{3}$ but how to connect it with the left side

I would be very grateful for any hint.

John Snow
  • 51

3 Answers3

6

Suppose you select three numbers $i<k<\ell$ from the $n+2$ numbers $\{-1,0,1, \dots,n\}$. Then $k$ ranges from $0$ to $n-1$. Once you fix $k$, there are $n-k$ choices for $\ell$ and $k+1$ choices for $i$. Thus, $$\sum_{k=0}^{n-1} (n-k)(k+1)={n+2 \choose 3} \,.$$

Yuval Peres
  • 21,955
  • I do not understand how this way of thinking corresponds to the summation to prove – John Snow Nov 07 '22 at 13:18
  • 2
    This is known as a bijective proof. We count the size of a set in two ways to get an identity. https://en.wikipedia.org/wiki/Bijective_proof#:~:text=of%20size%20n.-,A%20bijective%20proof,be%20denied%20ice%20cream%20cones. – Yuval Peres Nov 07 '22 at 17:07
  • 1
    Now, I can see this clearly. Thanks a lot! – John Snow Nov 07 '22 at 21:07
3

Hint:

$$\sum^{n-1}_{k=0}(n-k)(k+1)=\sum^{n-1}_{k=0}[n(k+1)-k^2+k]=n\sum^{n-1}_{k=0}[k+1]-\sum^{n-1}_{k=0}k^2+\sum^{n-1}_{k=0}k$$

Now try using facts about what $\sum^n_{k=1}k$ and $\sum^n_{k=1}k^2$ equal to.

Kyan Cheung
  • 3,184
0

Yuval gave a magnificent proof.

Here's an alternative approach:

$$ \sum_{k=0}^{n-1} (n-1)(k+1) = n \cdot \underbrace{ \sum_{k=0}^{n-1} (k + 1)}_{:= \, S_1} - \underbrace{\sum_{k=0}^{n-1} k(k + 1)}_{:= \, S_2} $$

Rewriting both these summations as the sum of binomial coefficients,

$$ S_1 = 1 +2 + \cdots + n = \binom 11 + \binom21 + \cdots + \binom n1 $$

$$ \frac{S_2}2 = \binom 22 + \binom32 + \cdots +\cdots + \binom n2 $$

By Hockey stick identity, $ S_1 = \binom {n+1}2 $ and $\frac {S_2}2 = \binom {n+1}3 $.

Can you finish it off from here?

GohP.iHan
  • 1,376