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.
 A: 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. 
A: 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}$$
A: 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=?$$
A: 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$$
A: $\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}}
$$

A: Here is a combinatorial approach: $\binom{m+1}{3}$ is the number of three element subsets of $\left\{ 0,1,...,m\right\}$. For $2 \leq n \leq m$ $\space\space$: $\binom{n}{2}$ is the number of three element subsets of $\left\{ 0,1,...,m\right\}$ whose biggest element is n, because we need to choose the remaining $2$ elements from the set $\left\{ 0,1,...,n-1\right\}$. Summing over all $n$ we get the righthand side $\sum_{n=2}^{m}\binom{n}{2}$, we start at $n = 2$ because the largest element of a three element set of  $\left\{ 0,1,...,m\right\}$ has to be at least $2$.
Thus the result follows.
A: Note that this is a special case of the more general:
$$\sum_{j=0}^{m}\binom{n+j}{n}=\binom{n+m+1}{n+1}=\binom{n+m+1}{m}$$
See proof
Specifically you can rewrite yours to fit into the above form as:
$$\sum_{n=2}^{m}\binom{n}{2}=\sum_{j=0}^{m-2}\binom{2+j}{2}=\binom{2+m-2+1}{2+1}=\binom{m+1}{3}$$
A: A slight generalization:
$$
\begin{align}
\sum_{k=0}^n\binom{k}{a}\binom{n-k}{b}
&=\sum_{k=0}^n\binom{k}{k-a}\binom{n-k}{n-k-b}\tag{1}\\
&=\sum_{k=0}^n(-1)^{n-a-b}\binom{-a-1}{k-a}\binom{-b-1}{n-k-b}\tag{2}\\
&=(-1)^{n-a-b}\binom{-a-b-2}{n-a-b}\tag{3}\\
&=\binom{n+1}{n-a-b}\tag{4}\\
&=\binom{n+1}{a+b+1}\tag{5}
\end{align}
$$
$(1)$: $\binom{n}{k}=\binom{n}{n-k}$
$(2)$: $\binom{n}{k}=(-1)^k\binom{k-1-n}{k}$
$(3)$: Vandermonde's Identity
$(4)$: $\binom{n}{k}=(-1)^k\binom{k-1-n}{k}$
$(5)$: $\binom{n}{k}=\binom{n}{n-k}$  

Use the identity above to show that
$$
\sum_{n=0}^m\binom{n}{2}\binom{m-n}{0}=\binom{m+1}{2+0+1}=\binom{m+1}{3}
$$
A: Consider Pascal's triangle.
$$\begin{array}{}&&&&1&&&&\\&&&1&&1&&&\\&&1&&2&&1&&\\&1&&3&&3&&1&\\1&&4&&6&&4&&1\end{array}$$
Note that any element in Pascal's Triangle is given by ${r \choose n}$ where $r$ is the row number (starting with $0$) and $n$ is the element's position in the row (starting with $0$).  Note that $n$ also corresponds to the diagonal the element lies on (e.g. if $n=0$, the element lies on the $0^{th}$ diagonal going from the top-right to the bottom-left).  You may also note that all elements in a row have the same sum of their diagonals (e.g. in row $4$, we have $(4,0),(3,1),(2,2),(1,3),$ and $(0,4)$ where $(a,b)$ is the numbers of the diagonals that intersect at that element).  Since the first element of row $r$ necessarily has $(a,b)=(r,0)$, we can deduce that the sum of the numbers of these diagonals is $r$ for any element in Pascal's Triangle.
Sorry, if that was confusing, but this is where it gets nice.
We can now substitute ${a+b \choose a}$ for ${r\choose n}$, starting with $b=0$.  Now, consider summing down a diagonal (which is equivalent to summing across $b$):
$$\begin{array}{}&&&&&1\\&&&&1&&1\\&&&1&&2&&\underline 1\\&&1&&3&&\underline 3&&1\\&1&&4&&\underline 6&&4&&1\\1&&5&&\underline{10}&&10&&5&&1\end{array}$$
Note that the first term is ${a\choose a}={a+1\choose a+1}=1$.  So instead we can consider summing the following:
$$\begin{array}{}&&&&&1\\&&&&1&&1\\&&&1&&2&&1\\&&1&&3&&\underline 3&&\underline 1\\&1&&4&&\underline 6&&4&&1\\1&&5&&\underline{10}&&10&&5&&1\end{array}$$
The sum ${x\choose y}+{x\choose y+1}={x+1\choose y+1}$, that is to say that any two adjacent elements of Pascal's Triangle produce the element below them.  It is clear then, that ultimately the sum of a diagonal will be the element in the next row beneath the last element in the sum that is not part of the diagonal.  This is called the hockey stick identity and better illustrations can be found here and here.
Anyway, $\sum_b {a+b\choose a}$, as demonstrated earlier, is actually the sum of a diagonal on the triangle, so $$ \sum_{b=0}^{k} {a+b\choose a}={a+k+1\choose a+1} $$
If we let $a=2$, $$\sum_{b=0}^{k-2} {b+2\choose 2}=\sum_{b=2}^k {b\choose 2}={2+(k-2)+1\choose 2+1}={k+1\choose 3}$$
A: Using the Gosper's algorithm (Maxima command
AntiDifference(binomial(n,2),n)),
$$\binom{n}2 = \frac{(n+1)^3-3(n+1)^2+2(n+1)}6 - \frac{n^3-3n^2+2n}6$$
and the sum telescopes:
$$
\sum_{n=2}^m\binom{n}2 = \frac{(m+1)^3-3(m+1)^2+2(m+1)}6 =
\frac{(m+1)m(m-1)}{1\,2\,3}.
$$
