Proving $\sum_i \binom{k}{k-i} \binom{n-k}{i} = \binom{n}{k}$

Question

I am in the middle of a probability question. The question is indeed simple. For the sake of clarity of the notation, I also include the question here, which is from Sheldon M. Ross's Introduction to Probability Models:

A fair coin is independently flipped $n$ times, $k$ times by A and $n-k$ times by B. Show that the probability that A and B flip the same number of heads is equal to the probability that there are a total of $k$ heads.

I have reduced the question to proving $$\sum_i \binom{k}{k-i} \binom{n-k}{i} = \binom{n}{k}$$ and I cannot move on. So far, I have tried to expand $\binom{k}{k-i}$ and $\binom{n-k}{i}$ by the definition of binomial coefficient and then observe for common terms. However, it comes out to be a mess and I am not sure if there is other way to do it.

Thanks in advance.

Answer 1

It is simply a matter of considering the coefficient of $x^{k}$ on both sides of $$ (1 + x)^{k} (1 + x)^{n-k} = (1 + x)^{n}. $$

Answer 2

If in a box there are $n$ marbles, $k$ of them being red and $n-k$ being black, with $$\sum_{i}\binom{n-k}{i}\binom{k}{k-i}$$ you are counting the ways to select $i$ black marbles and $k-i$ red marbles, for any possible $i$.

This is just the number of ways to select $k$ marbles out of $n$, i.e. $\binom{n}{k}$.

Answer 3

$\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{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{}$ \begin{align} \color{#66f}{\large\sum_{i}{k \choose k - i} {n - k \choose i}}& = \sum_{i}{n - k \choose i}\bracks{z^{k - i}}\pars{1 + z}^{k} = \bracks{z^{k}}\pars{1 + z}^{k}\sum_{i}{n - k \choose i}z^{i} \\[5mm] & = \bracks{z^{k}}\pars{1 + z}^{k}\,\pars{1 + z}^{n - k} = \bracks{z^{k}}\pars{1 + z}^{n} = \bbox[8px,border:1px groove navy]{\ds{n \choose k}} \end{align}