2
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Looks like someone beat me to it! :-) $\endgroup$ – ml0105 May 16 '16 at 17:35

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.