Show by counting two ways that $\sum_{i=1}^{n}i(n-i)=\sum_{i=1}^{n}{i\choose 2}={n+1 \choose 3}$?

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.