Proof by induction involving summation and combinations

Question

$$\sum_{m=2}^n {m \choose 2}={n+1 \choose 3}$$ for all $n \geq 2$.

Answer 1

We will use proof by induction for this problem.

First, we must solve for the base case $n=2$. Doing this we get ${2 \choose 2}={3 \choose 3}$ which is $1=1$, so our base case is satisfied.

Next we substitute $n+1$ in for $n$ giving us $$\sum_{m=2}^{n+1} {m \choose 2}={n+2 \choose 3}.$$

Using index shifting we have $$\sum_{m=2}^n {m \choose 2}+{n+1 \choose 2}={n+2 \choose 3}.$$

Subtracting the combination term to the other side gives us $$\sum_{m=2}^n {m \choose 2}={n+2 \choose 3}-{n+1 \choose 2}.$$

Finally, using Pascal's identity ${n \choose k}={n-1 \choose k} + {n-1 \choose k-1}$ our equation simplifies to $$\sum_{m=2}^n {m \choose 2}={n+1 \choose 3},$$ completing our proof.

Answer 2

A combinatorial argument:

There are $\binom {n+1}3$ ways to choose three elements from $\{1,\cdots, n+1\}$.

Any such triple has a maximal element which is at least $3$. If you specify that maximal element, call it $m+1$, then you must choose $2$ from $\{1,\cdots, m\}$ to complete the triple. Conversely, having chosen two numbers from $\{1,\cdots, m\}$ we get a selection of three from $\{1,\cdots, n+1\}$ by appending $m+1$. There are $\binom m2$ ways to choose the two smaller elements and $m$ runs from $2$ to $n$, so we are done.