Help proving a combinatorics result

Question

How do I prove $$\sum_{k=0}^n{m \choose k}{m \choose n-k} = {2m \choose n}\; \forall\; m>n$$ where $${a \choose b} \equiv \dfrac{a!}{b!(a-b)!}\; ?$$

It is clear to me intuitively why this should be the case. If I have $2m$ elements and have to choose $n$ objects from them, I can divide them into two groups of $m$ elements and choose $k$ from one and $n-k$ from another where $k \leq n$.

Answer 1

Hint:

$\dbinom mk$ is the coefficient of $x^k$ in the binomial expansion of $(1+x)^m$. So, calculate the coefficient of $x^n$ in the expansion of

• $(1+x)^{2m}$,
• $(1+x)^m(1+x)^m$,

and compare.

Answer 2

Refer to the Vandermonde's identity

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

You can also find a derivation from a concrete problem here.