Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

$$\sum_{0 \le k \le a}{a \choose k}{b \choose k} = {a+b \choose a}$$

Is there any way to prove it directly?

Using that $\displaystyle{a \choose k}=\frac{a!}{k!(a-k)!}$?

share|cite|improve this question

marked as duplicate by Davide Giraudo, Old John, Najib Idrissi, Dan Rust, Bruno Joyal Nov 16 '13 at 17:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

There is a very nice combinatorical proof without any calculations.

Note that ${a \choose k} = {a \choose a-k}$. So your sum is $$\sum_{0 \le k \le a}{a \choose a-k}{b \choose k}.$$ What does it mean? (what combinatorical objects does it count?) You choose $a-k$ elements from a $a$-element set and $k$ elements from a $b$-element set (you can do it in ${a \choose a-k}{b \choose k}$ ways). You do it with all possible $k$ ($\sum{a \choose a-k}{b \choose k}$). It's just choosing $a$ elements from the sum of those sets which has $a+b$ elements (${a+b \choose a}$).

share|cite|improve this answer

How about this proof? (Actually an extended version of your identity.)

I don't think it is "direct" enough, though...

share|cite|improve this answer
Why isn't it direct? I think it's fine, you deal with a polynomial and then substitute $x=1$. Btw. It seems that my proof is also on that wiki page - just below yours. – savick01 Feb 25 '12 at 17:48
What I mean by direct is using (ab)=a!/(a-b)!b! I am wondering is there any way to prove it by going to $$\sum_{0 \le k \le a} {a \choose k} {b \choose k} = \sum_{0 \le k \le a} \frac{a!}{k!(a-k)!} \frac{b!}{k!(b-k)!}$$ – KH Kim Feb 27 '12 at 13:30

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