Combinatorics Proof of $\sum_{i=0}^n \sum_{j=0}^{i-1} j = {n+1 \choose 3}$

Question

Proof of $\sum_{i=0}^n \sum_{j=0}^{i-1} j = {n+1 \choose 3}$

---

I am trying to generate a combinatorics proof of this identity, but have been stuck for hours. I've been trying to think of someway to describe building the number of subsets of size 3 of a set of size n-1 that also generates the sum on the left, but haven't made much progress.

Answer 1

Hints

How many subsets of $\{0,1,\dots,n\}$ have size $3$?

For how many of those subsets is the largest element equal to $i$, and the second largest equal to $j$?

Answer 2

Writing: $$j=\sum_{k=0}^{j-1} 1$$ you get: $$\sum_{i=0}^n \sum_{j=0}^{i-1} j = \sum_{i=0}^n \sum_{j=0}^{i-1} \sum_{k=0}^{j-1} 1$$

Now, notice the right side counts triples $(i,j,k)$ with: $$0\leq k<j<i\leq n.$$

Answer 3

Here is a combinatoric proof using the Binomial theorem (generalised).

First note that $\sum_{i=0}^n \sum_{j=0}^{i-1} j = \sum_{j=0}^{n} \sum_{i=j+1}^n j = \sum_{j=0}^{n} j (n-j) = \sum_{m=0}^{n} m (n-m)$. This looks like a convolution of terms, suggesting the multiplication of power series.

Note that ${x \over (1-x)^2} = \sum_{n=0}^\infty n x^n$ and ${x^2 \over (1-x)^4} = \sum_{n=0}^\infty n x^n \sum_{m=0}^\infty m x^m$, and using the convolution of terms, we get ${x^2 \over (1-x)^4} = \sum_{n=0}^\infty \sum_{m=0}^n m(n-m) x^n$.

Using the Binomial theorem, we have $x^2(1-x)^{-4} = \sum_{n=0}^\infty \binom{-4}{n} (-x)^{n+2}$.

If we suppose $n \ge 2$, we can compare coefficients of $x^n$ to get $\sum_{m=0}^n m(n-m) = \binom{-4}{n-2}(-1)^n$.

Expanding $\binom{-4}{n-2}(-1)^n = { (-4)(-5)\cdots (-(n+1))\over (n-1)!} = { 4 \cdot 5 \cdots (n+1)\over (n-1)!} = { (n+1)!\over 3!(n-1)!} = \binom{n+1}{3}$.