Show by counting two ways that $\sum_{i=1}^{n}i(n-i)=\sum_{i=1}^{n}{i\choose 2}={n+1 \choose 3}$? I'm trying to solve the following problem:



I am trying to understand what he is counting in two ways in the first and second equality. I noticed that ${i \choose 2}=\frac{i(i-1)}{2}$ is the sum of the first $(i-1)$ integers. I did the following:

*

*I expanded both sums and showed that they are equal.

*I wrote ${n+1 \choose 3}=\frac{(n+1)n(n-1)}{6}$ and showed it is equal to one of the sums.


But judging from the section where the author writes about counting in two ways, it seems something else should be done:






I struggled a lot to find a figure such as the one he found in this example. Although I understood that ${i \choose 2}=\frac{i(i-1)}{2}$ and hence that $\sum_{i=1}^{n} {i \choose 2}$ is the sum of the sums of the first $i$ integers, I couldn't match the first sum to it in any meaningful way, I also don't know how to match the sums to ${n+1 \choose 3}$.
 A: Write:

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5

Reading across gives the second series. Reading down gives the first.
In maths,
$$\sum_\limits{i=1}^{n-1} \sum_\limits{j=1}^i j = \sum_\limits{i=1}^{n-1} \sum_\limits{j=1}^{n-i} i$$
Replacing the $i$ and $j$ variables with $\sum_\limits{k=1}^j 1$ and $\sum_\limits{k=1}^i 1$ respectively gives three summations over $1$ with equal ranges.
Second to third is the Hockey Stick Theorem.
If we say the $n^{th}$ integer is the sum of $n\;1$'s, then the sum of $n$ integers is the sum of the sum of $n\;1$'s, and then the sum of $n$ sum of integers is the sum of the sum of the sum of $n\;1$'s.
$$\binom{n}{1}=\sum_\limits{i=1}^n 1$$
$$\binom{n}{2}=\sum_\limits{i=1}^{n-1} \sum_\limits{j=1}^i 1$$
$$\binom{n}{3}=\sum_\limits{i=1}^{n-2} \sum_\limits{j=1}^i \sum_\limits{k=1}^j 1$$
And in pictures:

1
1 1         1
1 1 1       1 1       1
1 1 1 1     1 1 1     1 1     1
1 1 1 1 1   1 1 1 1   1 1 1   1 1   1

A: I would add a third way: you may notice that $\sum_{k=1}^{n}k(n-k)=\sum_{k=1}^{n-1}k(n-k)$ is a convolution, namely
$$ \sum_{k=1}^{n-1}k(n-k) = [x^n]\left(\sum_{k\geq 1}k x^k\right)^2.\tag{1}$$
Stars&bars can be written in the following way:
$$ \frac{1}{(1-x)^{m+1}}=\sum_{n\geq 0}\binom{n+m}{m}x^n \tag{2} $$
hence by using $(1)$ once and $(2)$ twice we have:
$$ \sum_{k=1}^{n}k(n-k) = [x^n]\frac{x^2}{(1-x)^4}=[x^{n-2}]\frac{1}{(1-x)^4}=\binom{(n-2)+3}{3}=\binom{n+1}{3}\tag{3} $$
as was to be shown.
A: Consider choosing $3$ distinct numbers from $n+1$ numbers. Obviously there are $\binom{n+1}{3}$ way to do this.
Another way to count this: first choose $(i+1)$ as the second biggest number, then choose the smallest number from $(1,...,i)$ and choose the biggest number from $(i+2,...,n+1)$. $\sum_{i=1}^{n-1}{\ i(n-i)}$
Yet another way to count this: first choose $(i+1)$ as the biggest number, then choose the two smaller numbers from $(1,...,i)$. $\sum_{i=2}^{n}{\binom{i}{2}}$
Bonus: first choose $i+1$ as the smallest number, then choose the two bigger numbers from $(i+2,...,n+1)$. $\sum_{i=0}^{n-2}{\binom{n-i\ \ }{2}}$
$$
\binom{n+1}{3}=\sum_{i=1}^{n-1}{i(n-i)}=\sum_{i=2}^{n}{\binom{i}{2}}=\sum_{i=0}^{n-2}{\binom{n-i}{2}}
$$
