4
$\begingroup$

I would like to prove combinatorially that $\sum_{i=1}^ni\cdot(n-i) = \binom{n+1}{3}$.

Algebraically, this identity is easily proved in the following way:

$LHS = (1+2+\cdot\cdot\cdot+n-1+n)\cdot n - (1^2+2^2+\cdot\cdot\cdot+n^2)\\=n^2(n+1)/2 - n(n+1)(2n+1)/6 = (n+1)(n-1)\cdot n/6=RHS$

However, is there any combinatorial proof for this equality?

|cite|improve this question
$\endgroup$
  • $\begingroup$ What is "Combinatoric way"? $\endgroup$ – Krish Sep 14 '17 at 5:51
  • $\begingroup$ @Krish OP is presumably asking for a combinatorial proof of the identity. $\endgroup$ – JMoravitz Sep 14 '17 at 5:51
  • $\begingroup$ @JMoravitz thanks edited OP $\endgroup$ – Beverlie Sep 14 '17 at 5:52
10
$\begingroup$

Consider the three-element subsets of $\{0,1,\ldots,n\}$. There are $\binom{n+1}3$ of them. How many have "middle element" $i$? If the set has middle element $i$, there are $i$ choices for the smallest element and $n-i$ choices for the largest element, so there are $i(n-i)$ three-element subsets of $\{0,1,\ldots,n\}$ with middle element $i$.

|cite|improve this answer
$\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.