0
$\begingroup$

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$.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.