Evaluate $\sum_{k=0}^{n} {n \choose k}{m \choose k}$ for a given $n$ and $m$.

Question

How do I evaluate $\sum_{k=0}^{n} {n \choose k}{m \choose k}$ for a given $n$ and $m$.

I have tried to use binomial expansion and combine factorials, but I have gotten nowhere. I don't really know how to start this problem.

The answer is ${n+m \choose n}$. Any help is greatly appreciated.

EDIT: I'm looking for a proof of this identity.

Answer 1

Use the fact that (which follows from the definition) $$\binom{m}{k}=\binom{m}{m-k}.$$ Once you have this the LHS can be written as $$LHS=\sum_{k=0}^n\binom{n}{k}\binom{m}{k}=\sum_{k=0}^n\binom{n}{k}\binom{m}{m-k}.$$

Now we can do a combinatorial argument to find this sum. Consider a group of $n$ men and $m$ women. We want to make a committee consisting of $m$ people. This can be done in any of the following ways:

1). $0$ men and $m$ women-----this selection can be made in $\binom{n}{0}\binom{m}{m}$ ways.

2). $1$ man and $m-1$ women-----this selection can be made in $\binom{n}{1}\binom{m}{m-1}$ ways.

and so on.....

m+1). $m$ men and $0$ women-----this selection can be made in $\binom{n}{m}\binom{m}{0}$ ways.

The sum total of this gives you the LHS. But this problem can also be solved by considering choosing $m$ people out of a group of $m+n$ people, which can be done in $\binom{n+m}{m}$ ways. Hence the two ways of counting should be equal.

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

Answer 2

Using the Vandermonde Identity, this is $$ \sum_{k=0}^n\binom{n}{n-k}\binom{m}{k}=\binom{n+m}{n} $$

---

Proof of Vandermonde's Identity

$$ \begin{align} \sum_{k=0}^{m+n}\color{#C00000}{\binom{m+n}{k}}x^k &=(1+x)^{m+n}\tag{1}\\ &=(1+x)^m(1+x)^n\tag{2}\\ &=\sum_{j=0}^m\binom{m}{j}x^j\sum_{k=0}^n\binom{n}{k}x^k\tag{3}\\ &=\sum_{j=0}^m\sum_{k=j}^{n+j}\binom{m}{j}\binom{n}{k-j}x^k\tag{4}\\ &=\sum_{k=0}^{m+n}\color{#C00000}{\sum_{j=0}^k\binom{m}{j}\binom{n}{k-j}}x^k\tag{5} \end{align} $$ Explanation:
$(1)$: binomial theorem
$(2)$: property of exponents
$(3)$: binomial theorem
$(4)$: substitute $k\mapsto k-j$
$(5)$: change order of summation

Compare the coefficients of $x^k$.

Answer 3

Building on robjohn's answer, to prove the Vandermonde identity look at the coefficient of $x^n$ on both sides of the equality $$ (x+1)^n(x+1)^m = (x+1)^{m+n}. $$

Answer 4

Suppose we want to pick $n$ children from a group of $n$ boys and $m$ girls. Then we can pick $n$ boys and $0$ girls, or $n - 1$ boys and $1 $ girl, or $n - 2$ boys and $2$ girls, ... There are

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

ways to do this.

But we can also look at it as choosing $n$ objects from a set of $n + m$ objects. Then there are

$$\binom{n + m}{n}$$

ways to do this.

Since both are counting the same number of things, they must be equal, i.e.

$$\sum_{r = 0}^n\binom{n}{r}\binom{m}{r} = \binom{n + m}{n}$$

Answer 5

$\newcommand{\+}{^{\dagger}} \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{\down}{\downarrow} \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{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \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} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{\sum_{k=0}^{n}{n \choose k}{m \choose k}:\ {\large ?}}$

${\large\tt\mbox{Hereafter, I'll illustrate a general method:}}$

\begin{align}&\color{#66f}{\large\sum_{k=0}^{n}{n \choose k}{m \choose k}} =\sum_{k=0}^{n}{n \choose k}\oint_{\verts{z}\ =\ 1} {\pars{1 + z}^{m} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{m} \over z}\, \sum_{k=0}^{n}{n \choose k}\pars{1 \over z}^{k}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{m} \over z}\, \pars{1 + {1 \over z}}^{n}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{m + n} \over z^{n + 1}}\, \,{\dd z \over 2\pi\ic} = \color{#66f}{\large{m + n \choose n}} \end{align}