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

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.


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