3
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – dc3rd May 27 '16 at 20:55
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

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

$\endgroup$
  • $\begingroup$ I believe you were one of the first to present the Egorychev method at MSE. (+1). $\endgroup$ – Marko Riedel May 28 '16 at 22:13
  • $\begingroup$ @MarkoRiedel I don't know it's true. I was not aware it has a name. Fine to know that. Thanks. $\endgroup$ – Felix Marin May 28 '16 at 22:17
  • $\begingroup$ 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. $\endgroup$ – Marko Riedel May 28 '16 at 22:22
  • $\begingroup$ @MarkoRiedel Thanks. Maybe, I can buy it at Amazon. I learnt many tricks with Donald Knuth ( TeX author ) books. $\endgroup$ – Felix Marin May 28 '16 at 22:34
  • $\begingroup$ 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. $\endgroup$ – Marko Riedel May 28 '16 at 22:39

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.