# Combinatorial Proof Question: Vandermonde convolution identity

I'm really iffy on combinatorial proofs in general and now that there is a sum, it's just confused me even more. Can someone try and walk me through this proof?

$$\binom{m + n}{r} = \sum_{k=0}^r \binom{m}{k}\binom{n}{r - k}$$

• $$(1+x)^{m+n}=(1+x)^m(1+x)^n$$ – Lucian Feb 11 '14 at 0:28

## 2 Answers

There are $m$ men and $n$ women, and you need to pick a team of $r$ people. The LHS counts how many ways to do this directly, the RHS breaks this down into $k$ men and $r-k$ women.

• The LHS is pretty clear to me. It's unclear to me how the RHS breaks it down though. The sum is what is throwing me off. – user127778 Feb 10 '14 at 23:43
• Consider, say, $k=3$. Then ${m\choose 3}$ chooses three men, and ${n\choose r-3}$ chooses $r-3$ women. We multiply because those two choices are independent. – vadim123 Feb 10 '14 at 23:44

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}{\left\langle #1 \right\rangle}% \newcommand{\braces}{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}{\left\lbrack #1 \right\rbrack}% \newcommand{\ceil}{\,\left\lceil #1 \right\rceil\,}% \newcommand{\dd}{{\rm d}}% \newcommand{\down}{\downarrow}% \newcommand{\ds}{\displaystyle{#1}}% \newcommand{\equalby}{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}{\,{\rm e}^{#1}\,}% \newcommand{\fermi}{\,{\rm f}}% \newcommand{\floor}{\,\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}{\left\vert #1\right\rangle}% \newcommand{\ol}{\overline{#1}}% \newcommand{\pars}{\left( #1 \right)}% \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}{\underline{#1}}% \newcommand{\verts}{\left\vert\, #1 \,\right\vert}$ $\ds{{m + n \choose r} = \sum_{k=0}^{r}{m \choose k}{n \choose r - k}:\ {\large ?}}$.
Since $\ds{{n \choose r - k} = 0\ \mbox{when}\ k > r}$, we'll have $\ds{{m + n \choose r} = \sum_{k=0}^{m}{m \choose k}{n \choose r - k}}$

\begin{align} \color{#00f}{\large\sum_{k=0}^{r}{m \choose k}{n \choose r - k}}&= \sum_{k=0}^{m}{m \choose k}\sum_{\ell = 0}^{n}{n \choose \ell}\delta_{\ell, r - k} = \sum_{k=0}^{m}{m \choose k}\sum_{\ell = 0}^{n}{n \choose \ell} \int_{\verts{z} = 1}{1 \over z^{\ell - r + k + 1}}\,{\dd z \over 2\pi\ic} \\[3mm]&= \int_{\verts{z} = 1}\bracks{\sum_{k=0}^{m}{m \choose k}\pars{1 \over z}^{k}} \bracks{\sum_{\ell = 0}^{n}{n \choose \ell}\pars{1 \over z}^{\ell}} {1 \over z^{-r + 1}}\,{\dd z \over 2\pi\ic} \\[3mm]&= \int_{\verts{z} = 1}\pars{1 + {1 \over z}}^{m} \pars{1 + {1 \over z}}^{n}\,{1 \over z^{-r + 1}}\,{\dd z \over 2\pi\ic} = \int_{\verts{z} = 1} {\pars{1 + z}^{m + n} \over z^{m + n - r + 1}}\,{\dd z \over 2\pi\ic} \\[3mm]&= \sum_{\ell = 0}^{m + n}{m + n \choose \ell}\int_{\verts{z} = 1} {z^{\ell} \over z^{m + n - r + 1}}\,{\dd z \over 2\pi\ic} = \sum_{\ell = 0}^{m + n}{m + n \choose \ell}\delta_{\ell,m + n - r} \\[3mm]&={m + n \choose m + n - r} =\color{#00f}{\large{m + n \choose r}} \end{align}