Help with proof that $ \sum_{i=0}^k{k \choose i}{N-k \choose n-i} = {N \choose n} $ 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} $
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}.$$
$\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} &amp; =
\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] &amp; =
\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}