2
$\begingroup$

Show that $\,\displaystyle\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$.

I'm thinking right now (though not getting anywhere with it) that I want to expand out the summation portion to $i!/2!(i-2)!$ and simplify from there? Not sure if that will help, not to mention if I put $1$ in for $i$ I get $1/-2$ which I don't think is right.

Anyone care to shed some light on the subject?

Thanks.

$\endgroup$
  • $\begingroup$ It's actually from $i=2$ and here, proved it: ideone.com/Tq36eW (n > 0 apparently). $\endgroup$ – Shahar Mar 10 '14 at 23:01
  • $\begingroup$ as i commented on the top answer below, the problem i am trying to solve is i=1, not i=2, thanks $\endgroup$ – user3216655 Mar 10 '14 at 23:39
  • $\begingroup$ @user3216655 The other users answered the question you wrote in the original title, but it seems that you want to know how to calculate $\binom{1}{2}$. I changed your title and gave an explanation below. $\endgroup$ – Théophile Mar 11 '14 at 0:44
  • $\begingroup$ $\binom{n}{m}=0$ if $m>n$. This is true both combinatorially (a set of size $n$ has no subsets of size $m>n$) and algebraically using the polynomial definition $n(n-1)\cdots(n-n)\cdots(n-m+1)/m!=0$. $\endgroup$ – blue Mar 11 '14 at 0:51
11
$\begingroup$

What we shall show is that $$ \sum_{i=2}^n\binom{i}{2}=\binom{n+1}{3}, $$ using a combinatorial argument:

The right-hand side is the number of the ways to choose three numbers among $\{1,2,\ldots,n,n+1\}$.

This is equal to the sum of $P_i$'s, $i=2,\ldots,n$, where $P_i$ is the number of ways to choose three numbers among $\{1,2,\ldots,n,n+1\}$ with the largest one being $i+1$. But $P_i$ is the number of ways to choose two numbers among $\{1,2,\ldots,i\}$, which is equal to $\binom{i}{2}$. Hence $$ \binom{n+1}{3}=\binom{2}{2}+\binom{3}{2}+\cdots+\binom{n}{2}. $$

$\endgroup$
  • $\begingroup$ that's not what i want to show, although i appreciate the answer. the question, as per the text is i=1, i appreciate the answer but the problem i'm having is dealing with it being i=1 (i understand it with i=2, not with 1) thanks $\endgroup$ – user3216655 Mar 10 '14 at 23:33
  • $\begingroup$ This doesn't answer the question. $\endgroup$ – Ink Mar 11 '14 at 0:50
  • $\begingroup$ @user3216655, this shows that the original question is wrong (typo?). $\endgroup$ – vonbrand Mar 11 '14 at 1:40
  • $\begingroup$ @vonbrand the original question is not wrong, all i'm saying is the first couple people answered the wrong question, i=1 in my question, but others answered the right question below $\endgroup$ – user3216655 Mar 11 '14 at 1:55
2
$\begingroup$

The question seems to be about how to calculate $\binom{1}{2}$. In general, for $n,k \geq 0$, the binomial coefficient can be defined to be the coefficient of $x^k$ in the expansion of $(1+x)^n$. In other words, $\binom{1}{2}$ is the coefficient of $x^2$ in $(1+x)^1$. But this coefficient is 0. Hence $\binom{1}{2} = 0$, which is why this doesn't affect the validity of the proofs in the other answers.

As another way to think about it, $\binom{1}{2}$ counts the number of ways to choose $2$ objects from a set of $1$; there are no such ways. In general, $\binom{n}{k} = 0$ for $k > n \geq 0$.

$\endgroup$
  • 1
    $\begingroup$ Or: $\binom{i}{2}=i(i-1)/2$, which is $0$ when $i=1$. $\endgroup$ – David Mar 11 '14 at 0:46
1
$\begingroup$

Hint. The basic Pascal's triangle identity is $$\binom{i+1}{k}=\binom{i}{k}+\binom{i}{k-1}\ .$$ Taking $k=3$ and rearranging, $$\binom{i}{2}=\binom{i+1}{3}-\binom{i}{3}\ .$$ Therefore the sum is $$\sum_{i=1}^n \left[\binom{i+1}{3}-\binom{i}{3}\right]\ ,$$ which is a telescoping sum.

$\endgroup$
1
$\begingroup$

$$\sum_{i=2}^n\binom{i}{2}=\binom{2}{2}+\binom{3}{2}+\binom{4}{2}+\binom{5}{2}+\cdots+\binom{n}{2}$$

Since $\binom22=\binom33$

$$\sum_{i=2}^n\binom{i}{2}=\binom{3}{3}+\binom{3}{2}+\binom{4}{2}+\binom{5}{2}+\cdots+\binom{n}{2}$$

Pascal's Triangle Identity states that

$$\binom{n-1}k+\binom{n-1}{k-1}=\binom{n}{k}$$

So,

$$\sum_{i=2}^n\binom{i}{2}=\color{red}{\binom{3}{3}+\binom{3}{2}}+\binom{4}{2}+\binom{5}{2}+\cdots+\binom{n}{2}$$

$$\sum_{i=2}^n\binom{i}{2}=\color{red}{\binom{4}{3}}+\binom{4}{2}+\binom{5}{2}+\cdots+\binom{n}{2}$$

$$\sum_{i=2}^n\binom{i}{2}=\color{green}{\binom{4}{3}+\binom{4}{2}}+\binom{5}{2}+\cdots+\binom{n}{2}$$

$$\sum_{i=2}^n\binom{i}{2}=\color{green}{\binom{5}{3}}+\binom{5}{2}+\cdots+\binom{n}{2}$$

So on and so forth, until we have

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

$\endgroup$
1
$\begingroup$

Well, if $n-1 =2k$ $$\displaystyle\sum_{i=1}^{n} \binom{i}{2} = \displaystyle\sum_{i=1}^{n}\frac{i\cdot (i-1)}{2}=\frac{1\cdot 0}{2}+\frac{2\cdot 1}{2}+\frac{3\cdot 2}{2}+\frac{4\cdot 3}{2} + \ldots +\frac{n\cdot (n-1)}{2} = \frac{2\cdot 1+3\cdot 2+4\cdot 3+ \ldots +n\cdot (n-1)}{2} = \frac{2^2\cdot2+4^2\cdot2+6^2\cdot2+\ldots +(n-1)^2\cdot2}{2}=2^2+4^2+6^2+\ldots+(n -1)^2=4(1+2^2+3^2+\ldots+k^2)=\frac{4k\cdot(k+1)\cdot(2k+1)}{6}=\frac{4\frac{n-1}{2}\cdot\frac{n+1}{2}\cdot n}{6} = \frac{(n+1)\cdot n\cdot(n-1)}{3!}=\binom{n+1}{3}$$ Similarly if $n-1 =2k +1$ you have $$\displaystyle\sum_{i=1}^{n} \binom{i}{2} = \displaystyle\sum_{i=1}^{n}\frac{i\cdot (i-1)}{2}=\frac{1\cdot 0}{2}+\frac{2\cdot 1}{2}+\frac{3\cdot 2}{2}+\frac{4\cdot 3}{2} + \ldots +\frac{n\cdot (n-1)}{2} = \frac{2\cdot 1+3\cdot 2+4\cdot 3+ \ldots +n\cdot (n-1)}{2} = \frac{2^2\cdot2+4^2\cdot2+6^2\cdot2+\ldots +(n-2)^2\cdot2+n\cdot(n-1)}{2}=2^2+4^2+6^2+\ldots+(n-2)^2+n\cdot (n-1)=4(1+2^2+3^2+4^2+\ldots+(n-2)^2)+\frac{n\cdot(n-1)}{2}=\frac{4k\cdot(k+1)\cdot(2k+1)}{6}+\frac{n\cdot(n-1)}{2}=\frac{4\frac{n-2}{2}\cdot\frac{n}{2}\cdot (n-1)}{6}+\frac{n\cdot(n-1)}{2}=\frac{(n-2)\cdot n\cdot(n-1)}{3!}+\frac{n\cdot(n-1)}{2}=\frac{n\cdot(n-1)\cdot(n-2)+3n\cdot(n-1)}{3!}=\frac{n\cdot(n-1)\cdot(n-2+3)}{3!}=\frac{n\cdot(n-1)\cdot(n+1)}{3!}=\binom{n+1}{3}$$

$\endgroup$
1
$\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_{i = 1}^{n}{i \choose 2} = {n + 1 \choose 3}:\ {\large ?}}$

\begin{align} \color{#00f}{\large\sum_{k = 1}^{n}{k \choose 2}}&=\sum_{k = 1}^{n} \int_{\verts{z} = 1} {\pars{1 + z}^{k} \over z^{3}}{\dd z \over 2\pi\ic} =\int_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z^{3}} \sum_{k = 1}^{n}\pars{1 + z}^{k} \\[3mm]&=\int_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z^{3}}\, {\pars{1 + z}\bracks{\pars{1 +z}^{n} - 1} \over \pars{1 +z} - 1} \\[3mm]&=\underbrace{% \int_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{\pars{1 + z}^{n + 1} \over z^{4}}} _{\ds{=\ {n + 1 \choose 3}}}\ -\ \overbrace{\int_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 + z \over z^{4}}} ^{\ds{=\ 0}} =\color{#00f}{\large{n + 1 \choose 3}} \end{align}

$\endgroup$
0
$\begingroup$

The process of choosing all combinations of three from $n+1$ can be thought about like this:

If we define $e_i$ to be the ith element,

  1. Choose $e_1$ and then choose 2 other elements from the rest. These would be all combinations that have $e_1$ as a choice.

  2. Choose $e_2$ as an element and then choose 2 other elements from the n-1 after $e_2$. These would be all combinations that have $e_2$ as a choice, but not $e_1$, as it was already counted.

  3. Choose $e_3$ as an element and then choose 2 others from the n-2 after $e_3$. These would be all combinations that have $e_3$ as a choice, excluding $e_1$ and $e_2$ since they were already counted.

...

$\endgroup$

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.