13
$\begingroup$

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

Thanks in advance for any help.

$\endgroup$
  • $\begingroup$ Sorry was looking at a different question! Will edit it now! $\endgroup$ – Crockett Nov 27 '13 at 16:48
  • $\begingroup$ Induction on $m$ is straightforward. $\endgroup$ – Daniel Fischer Nov 27 '13 at 16:49
  • $\begingroup$ @nayrb $n$ is the iterant in the sum, you should be taking the limit as $m$ tends to $\infty$, in which case both sides diverge. $\endgroup$ – Tim Ratigan Nov 27 '13 at 16:56
  • $\begingroup$ This question and almost all of the upvoted answers have been downvoted in the period of about one minute. It does not seem that any of these downvotes were about the quality of the answers. The most reasonable explanation for this mass downvote would be lack of context in the question. However, this question and most of the answers were posted long before any concern about PSQs or context were raised. $\endgroup$ – robjohn Jun 21 '18 at 14:39

11 Answers 11

12
$\begingroup$

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$$

$\endgroup$
  • 1
    $\begingroup$ +1 . If you look at the last person, if the last person is $a_{n+1}$ then $n\geq 2$ and there are exactly $\binom{n}{2}$ ways of choosing the first two kids. It is exactly the same argument, but you get directly $$\sum_{n=2}^m \binom{n}{2}$$ $\endgroup$ – N. S. Nov 27 '13 at 17:15
  • $\begingroup$ great answer, because it shows that '...if $a_j$ is the first person...' fully partitions the search space and hence equivalent to $\binom{n+1}{3}$ $\endgroup$ – Alex Sep 15 '17 at 21:40
10
$\begingroup$

$\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}} $$

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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}$$

$\endgroup$
2
$\begingroup$

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=?$$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$
0
$\begingroup$

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}$$

$\endgroup$
0
$\begingroup$

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} $$

$\endgroup$
0
$\begingroup$

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}. $$

$\endgroup$
-1
$\begingroup$

If the identity is true, we can rewrite this specific case of the well-known addition formula $$\binom m3+\binom m2=\binom{m+1}3$$ as the trivial recurrence $$\sum_{n=2}^{m-1} \binom{n}{2}+\binom m2=\sum_{n=2}^m \binom{n}{2}.$$

$\endgroup$
  • $\begingroup$ Can it be made simpler ? $\endgroup$ – Yves Daoust Apr 15 '15 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.