# Prove that $\binom{m+n}{m}=\sum\limits_{i=0}^m \binom{m}{i}\binom{n}{i}$

I need to proof this following equality :

$$\binom{m+n}{m}=\sum_{i=0}^m \left(\binom{m}{i}\binom{n}{i}\right)$$

This is what I did combinatoric proof:

Left : subset with $m$ members from $m+n$

Right : $\binom{m}{i} \rightarrow$ The number of subsets in set $m$ could also be written as $2^m$ AND $\binom{n}{i} \rightarrow$ the number of subsets with $m$ members from set $n$

In case $n \leq m \implies \binom{n}{i}=2^n$

So this is what I came up with I still can't see why those expression are equal.

Any ideas? Thanks.

They aren’t equal. I’m afraid that your argument makes no sense: $\binom{m}i$ is the number of $i$-element subsets of $[m]$ and is certainly not $2^m$, and $\binom{n}i$ is not the number of $m$-element subsets of $[n]$ unless $i$ happens to equal $m$.

Suppose that you have $m$ men and $n$ women, and you want to choose a committee of $m$ people from this group; clearly $\binom{m+n}m$ is the number of possible committees. Now rewrite the righthand side as

$$\sum_{i=0}^m\binom{m}{m-i}\binom{n}i\;.$$

(Why is this equal to the original righthand side?)

For each $i\in\{0,1,\ldots,m\}$, $\binom{n}i$ is the number of ways to choose $i$ women, and $\binom{m}{m-i}$ is the number of ways to choose $m-i$ men to fill out a committee of $m$ people. Thus, $\binom{m}{m-i}\binom{n}i$ is the number of $m$-person committees that have exactly $i$ women. Summing over the possible values of $i$ gives you the total number of $m$-person committees that can be formed from this collection of $m$ men and $n$ women.

$\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{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ \begin{align} \sum_{k = 0}^{m}{m \choose k}{n \choose k} & = \sum_{k = 0}^{m}{m \choose k}{n \choose n - k} = \sum_{k = 0}^{m}{m \choose k}\ \overbrace{\oint_{\verts{z} = 1} {\pars{1 + z}^{n} \over z^{n - k + 1}}\,{\dd z \over 2\pi\ic}} ^{\ds{{n \choose n - k}}} \\[3mm] & = \oint_{\verts{z} = 1} {\pars{1 + z}^{n} \over z^{n + 1}}\ \overbrace{\sum_{k = 0}^{m}{m \choose k}z^{k}}^{\ds{\pars{1 + z}^{m}}}\ \,{\dd z \over 2\pi\ic} = \oint_{\verts{z} = 1}{\pars{1 + z}^{m + n} \over z^{n + 1}} \,{\dd z \over 2\pi\ic} = \color{#f00}{{m + n \choose n}} \end{align}
Observe that $\binom{m}{i} = \binom{m}{m-i}$. So you select $i$ folks from the $n$ person set and $m-i$ folks from the $m$ person set. These selections are independent, so by rule of product, me multiply. By rule of sum, we add up over all such $i$.