# prove $\sum_{k = 0}^{n} \binom{n}{k} \binom{m-n}{n-k} = \binom{m}{n}$

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

Attempt:I was thinking of trying to prove this through induction, but I am having trouble with a base case:

base case: let $n = 2$: $$LHS = \binom{2}{0} \binom{m-2}{2} + \binom{2}{1} \binom{m-2}{1} + \binom{2}{2} \binom{m-2}{0} \\ = \frac{(m-2)[(m-3) + 2!2!(m-3)!] + 2!}{2!} \ (after\ simplification)$$

$$RHS = \frac{m!}{2!(m-2)!}$$

But I am stuck as what to try next to at least equate these two expressions.

Note: I took a look at Vandermonde's identity on wikipedia and the ensuing proof, but the proof still leaves out how to make the transition between the two initial expressions

• What seems to be the problem in using Vandermonde's idendity? Should work is it not? – Satish Ramanathan May 27 '16 at 17:09

Use Pascal’s identity a few times:

\begin{align*} \binom20\binom{m-2}2+\binom21\binom{m-2}1+\binom22\binom{m-2}0&=\binom{m-2}2+2\binom{m-2}1+\binom{m-2}0\\ &=\left(\binom{m-2}2+\binom{m-2}1\right)+\\ &\qquad\qquad\left(\binom{m-2}1+\binom{m-2}0\right)\\ &=\binom{m-1}2+\binom{m-1}1\\ &=\binom{m}2\;. \end{align*}

But why start at $n=2$? Starting at $n=0$ makes the base case very simple.

• I was curious to see the expressions in "action", like you said $n = 0$ is easy, but you don't get to see anything really going on. – dc3rd May 27 '16 at 20:55

A much easier approach would be to look at both sides as the coefficient of $x^n$ in the binomial expansion of $(1+x)^m$.

The right hand side follows immediately.

For the left hand side, write $(1+x)^m$ as $(1+x)^n$$(1+x)^{m-n}$ and use the binomial theorem for each term in the product individually.

The coefficient for $x^n$ in this case is precisely the expression on the left hand side.

Combinatorics proof: From a group of $m$ people (among which $n$ are left-handed) we can pick a committee of $n$ people by picking $k$ left-handers and $n-k$ right-handers, $0\le k\le n$.

$\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}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\, #2 \,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$

\begin{align} \color{#f00}{\sum_{k = 0}^{n}{n \choose k}{m - n \choose n - k}} & = \sum_{k = 0}^{n}{n \choose k}\ \overbrace{\oint_{\verts{z} = 1}{\pars{1 + z}^{m - n} \over z^{n - k + 1}} \,{\dd z \over 2\pi\ic}}^{\ds{{m - n \choose n - k}}}\ =\ \oint_{\verts{z} = 1}{\pars{1 + z}^{m - n} \over z^{n + 1}}\ \overbrace{\sum_{k = 0}^{n}{n \choose k}z^{k}}^{\ds{\pars{1 + z}^{n}}}\ \,{\dd z \over 2\pi\ic} \\[3mm] & =\ \underbrace{% \oint_{\verts{z} = 1}{\pars{1 + z}^{m} \over z^{n + 1}} \,{\dd z \over 2\pi\ic}}_{\ds{{m \choose n}}}\ =\ \color{#f00}{{m \choose n}} \end{align}

• I believe you were one of the first to present the Egorychev method at MSE. (+1). – Marko Riedel May 28 '16 at 22:13
• @MarkoRiedel I don't know it's true. I was not aware it has a name. Fine to know that. Thanks. – Felix Marin May 28 '16 at 22:17
• If you have access to a university library you may consult "Integral representation and the computation of combinatorial sums" by G. P. Egorychev, translation published by the AMS. – Marko Riedel May 28 '16 at 22:22
• @MarkoRiedel Thanks. Maybe, I can buy it at Amazon. I learnt many tricks with Donald Knuth ( TeX author ) books. – Felix Marin May 28 '16 at 22:34
• Clearly we may suppose that D. Knuth deploys this method as it is basically the Cauchy Residue Theorem, but I believe it was Egorychev who wrote a book about it and put its detailed workings on an algorithmic footing. Many well-known mathematicians have used complex variables in combinatorics. – Marko Riedel May 28 '16 at 22:39