Help with proof that $ \sum_{i=0}^k{k \choose i}{N-k \choose n-i} = {N \choose n} $

Question

I would appreciate if somebody could give me a hint for the following problem. I'm seeking a combinatorial proof for:

$ \sum_{i=0}^k{k \choose i}{N-k \choose n-i} = {N \choose n} $

Answer 1

Suppose $k \leq N-k $. Then if you want to choose $k$ people, you can choose $i$ men in $\displaystyle{k\choose i}$ ways and $(k-i)$ women in $\displaystyle{N-k\choose k-i}$ ways , for $i\in\{0,1,\dots n\}.$

Then we have $$\sum_{i=0}^{k}{k\choose i}{N-k\choose k-i}={N\choose k}.$$

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \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{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#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} \sum_{i = 0}^{k}{k \choose i}{N - k \choose n - i} & = \sum_{i = 0}^{k}{k \choose i}\bracks{z^{n - i}}\pars{1 + z}^{N - k} = \bracks{z^{n}}\pars{1 + z}^{N - k}\sum_{i = 0}^{k}{k \choose i}z^{i} \\[5mm] & = \bracks{z^{n}}\pars{1 + z}^{N - k}\pars{1 + z}^{k} = \bracks{z^{n}}\pars{1 + z}^{N} = \bbx{N \choose n} \end{align}