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

Question

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.

Answer 1

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