Showing that $\sum\limits_{k=2}^n {k\choose2} = {{n+1}\choose 3}$ for integers $n\geq 2$

Question

I'm trying to prove that $\sum\limits_{k=2}^n {k\choose2} = {{n+1}\choose 3}$ for integers $n\geq 2$.

I figured induction was the way to go, so I tried. This is what I've accomplished so far:

Proved it holds for $n=2$.

Assumed it holds for some $n = q$

Used the assumption to get the following:

$$\sum\limits_{k=2}^{q+1}{k\choose2} = {{q+1}\choose 3}+{{q+1}\choose 2}$$

My goal is to prove that this equals $\displaystyle{{q+2}\choose 3}$ but I can't quite get there. I've expanded the binomial coefficients, but it's a mess.

Looking for help on completing the proof. Of course, in the name of curiosity, other neat methods are also welcome!

Answer 1

Although this is a standard identity for binomial coefficients and @Did's answer was also standard, here's a combinatorial explanation:

How many ways to choose 3 numbers out of $\{1,2,\cdots,q+2\}$

1. If $q+2$ is chosen, there are $\binom{q+1}{2}$ ways.
2. If $q+2$ is not chosen, there are $\binom{q+1}{3}$ ways.

Note that one can generalize the above argument to the following.

---

How many ways to choose $3$ numbers $a_1<a_2<a_3$ out of $\{1,2,\dots, n+1\}$?

Of course $a_3$ can only take values in $3,4,\dots, n+1$. For each $k=3,4,\dots, n+1$ there are $\binom{k-1}{2}$ choices of $a_1<a_2$. Add up all the cases we have $$\sum^{n+1}_{3}\binom{k-1}{2}=\binom{n+1}3.$$

Answer 2

Plug $n=q+1$ and $k=2$ into the identity $${n\choose k+1}+{n\choose k}=\frac{n-k}{k+1}{n\choose k}+{n\choose k}=\frac{n+1}{k+1}{n\choose k}={n+1\choose k+1}.$$

Answer 3

For binomial coefficients (as can be seen from the Pascal Triangle), the following identity holds: $$\require{cancel} {k\choose r}={k+1\choose r+1}-{k\choose {r+1}}$$

Summing by telescoping: $$\begin{align}\sum_{k=r}^{n}{k\choose r}&=\sum_{k=r}^{n}\left[{k+1\choose r+1}-{k\choose {r+1}}\right]\\ &=\quad {r+1\choose r+1} -\cancelto{0}{ {r\choose r+1}}\\ &\quad +{r+2\choose r+1} -{r+1\choose r+1}\\ &\quad +{r+3\choose r+1} -{r+2\choose r+1}\\ &\quad \cdots\\ &\quad +{n\choose r+1}\ \ -{n-1\choose r}\\ &\quad +{n+1\choose r+1}\ \ -{n\choose r+1}\\ &=\quad {n+1\choose r+1} \end{align}$$

Put $r=2$:

$$\sum_{k=2}^{n}{k\choose 2}={n+1\choose 3}\qquad \blacksquare $$