3
$\begingroup$

I'm having some trouble in finding a combinatorial way to prove the following expression:

$$\sum_{i=1}^n {i(n-i+1)} = {n+2 \choose 3}$$

I assume proving it in an algebraic way using the choose formula and induction is not too hard, but a combinatorial proof is what I'm seeking.

$\endgroup$
1
$\begingroup$

We look at the number of ways to choose $3$ numbers out of a set of $n + 2$ numbers $\{ 0, 1, 2, \dots, (n + 1)\}$.

Suppose that the second-smallest number that we choose is $k$. Then there are $k$ options for the smallest number, and $n + 1 - k$ options for the largest number. Now sum up over the possible values for $k$.

$\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.