How to show $\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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.

...

Answer 6

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

Answer 7

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