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.
 A: 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.
For more information, see the Wikipedia article on Vandermonde’s identity.
A: $\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}
A: 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$.
