Show that $ \sum_{n=2}^m \binom{n}{2} = \binom{m+1}{3}$

I need a hand in showing that $$ \sum_{n=2}^m \binom{n}{2} = \binom{m+1}{3}$$

Thanks in advance for any help.

Solution 1:

Heres a nice combinatorial proof: Lets say you have $n+1$ kids, and want to form a committee of three. Order the kids $a_1, a_2, \cdots, a_{n+1}$. There are $\dbinom{n+1}{3}$ ways to form the committee. On the other hand, if $a_1$ is the first person on the committee, we need to choose two more, in $\dbinom{n}{2}$ ways. If $a_2$ is the first person on the committee, we can choose two more in $\dbinom{n-1}{2}$ ways. In general, if $a_n$ is the first person on the committee, we can choosse two more in $\dbinom{n-k+1}{2}$ ways. Therefore, we have $$ \dbinom{n+1}{3} = \sum_{i=1}^{n+1} \dbinom{n-k+1}{2} = \dbinom{n}{2} + \dbinom{n-1}{2} + \cdots + \dbinom22$$

Solution 2:

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{\sum_{n = 2}^{m}{n \choose 2} = {m + 1 \choose 3}:\ {\large ?}}$

We'll use the identity: $$ {s \choose k} =\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{s} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} $$

\begin{align} \sum_{n = 2}^{m}{n \choose 2}&=\sum_{n = 2}^{m}\oint_{\verts{z}\ =\ 1} {\pars{1 + z}^{n} \over z^{3}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1}{1 \over z^{3}}\sum_{n = 2}^{m}\pars{1 + z}^{n} \,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ 1}{1 \over z^{3}} \,{\pars{1 + z}^{2}\bracks{\pars{1 + z}^{m - 1} - 1} \over \pars{1 + z} - 1} \,{\dd z \over 2\pi\ic} \\[3mm]&=\overbrace{\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{m + 1} \over z^{4}} \,{\dd z \over 2\pi\ic}}^{\ds{=\ {m + 1 \choose 3}}}\ -\ \overbrace{\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{2} \over z^{4}} \,{\dd z \over 2\pi\ic}}^{\ds{=\ 0}} \end{align}

$$\color{#00f}{\large% \sum_{n = 2}^{m}{n \choose 2} = {m + 1 \choose 3}} $$

Solution 3:

There is a roughly speaking universal mechanical method to prove such identities, once the result is guessed.

We calculate $\binom{k+1}{3}-\binom{k}{3}$. This is $\frac{(k+1)(k)(k-1)}{6} -\frac{k(k-1)(k-2)}{6}$. Take out the common factor $\frac{k(k-1)}{6}$ and simplify. We get $\binom{k}{2}$.

It follows that the sum on the left is equal to $$\binom{3}{3}-\binom{2}{3}+ \binom{4}{3}-\binom{3}{3}+ \binom{5}{3}-\binom{4}{3}+ \cdots +\binom{m+1}{3}-\binom{m}{3}.$$ Note the mass cancellation (telescoping). This always happens.

Remark: Many of the identities students are asked to prove in their first exposure to induction yield to the above procedure. Although in principle the mass cancellation requires induction, that makes such identities poor examples.

Solution 4:

For $m=2$, it amounts to proving $\binom{2}{2} = \binom{3}{3}$, which is true since both equal $1$.

Induction step: let's assume the formula is true for a given $m$, $$\sum_{n=2}^m \binom{n}{2}=\binom{m+1}{3}$$

Then,

$$\sum_{n=2}^{m+1} \binom{n}{2} = \sum_{n=2}^{m} \binom{n}{2} + \binom{m+1}{2}$$ $$=\binom{m+1}{3}+\binom{m+1}{2}=\binom{m+2}{3}$$

And you are done, by induction.

By the way, the same reasoning would give you for any $k \ge 0$,

$$\sum_{n=k}^m \binom{n}{k} = \binom{m+1}{k+1}$$

For a better understanding of what it means, I suggest you draw Pascal's triangle and see the sum of binomial coefficients in a column, then the sum is at the bottom of this column, one step downward and one step to the right, as in the following:

$$ \begin{array}{cccccccc} 1 & & & & & & &\\ 1 & 1 & & & & & &\\ 1 & 2 & \color{red}{1} & & & & &\\ 1 & 3 & \color{red}{3} & 1 & & & &\\ 1 & 4 & \color{red}{6} & 4 & 1 & & &\\ 1 & 5 & \color{red}{10} & 10 & 5 & 1& & &\\ 1 & 6 & \color{red}{15} & 20 & 15 & 6& 1& &\\ 1 & 7 & 21 & \color{blue}{35} & 35 & 21& 7& 1&\end{array}$$

Solution 5:

As $\displaystyle\binom n2=\frac{n(n-1)}2=\frac12\cdot n^2-\frac12\cdot n$

$$\sum_{2\le n\le m}\binom n2=\frac12 \sum_{2\le n\le m}n^2-\frac12\sum_{2\le n\le m} n$$

$$=\frac12\left( \sum_{1\le n\le m}n^2-1\right)-\frac12\left(\sum_{1\le n\le m} n-1\right)$$

$$=\frac12 \frac{m(m+1)(2m+1)}6-\frac12\frac{m(m+1)}2$$

$$=\frac{m(m+1)(2m+1)-3m(m+1)}{12}$$ $$=\frac{(m+1)m}{12}(2m+1-3)=\frac{(m+1)m(m-1)}6=?$$