Evaluate $\sum_{k=0}^{n} {n \choose k}{m \choose k}$ for a given $n$ and $m$. 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.
 A: $\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}
A: 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}.
$$
A: 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}$$
A: 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}$$ 
A: 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$.
