Sheldon Ross

Question

Prove

$\binom{m+n}{r}$ = $\binom{n}{0}\binom{m}{r}+\binom{n}{1}\binom{m}{r-1}+... +\binom{n}{r}\binom{m}{0}$

Comments

u can take any value and can check

like m=3

n=2 and r=2

here one thing missing in question r=min(m,n)

---

verification is easy but how to derive LHS from RHS or RHS from LHS ?

Answer 1

This is essentially selecting $r$ people from $n$ men and $m$ women.

i.e

Select $r$ people from $m + n$ = $\binom{m+n}{r}$

which is equal to $\Rightarrow$ (Select $0$ men and Select $r$ women) OR (Select $1$ man and Select $r-1$ women) OR $\cdots$ (Select $r$ men and Select $0$ women).

$\Rightarrow$ $\binom{n}{0}\binom{m}{r}+\binom{n}{1}\binom{m}{r-1}+... +\binom{n}{r}\binom{m}{0}$

$\therefore$ $\binom{m+n}{r} = \binom{n}{0}\binom{m}{r}+\binom{n}{1}\binom{m}{r-1}+... +\binom{n}{r}\binom{m}{0}$

Comments

@Neelay Upadhyaya

what you said is given in book itself and I know it,

can you mathematically prove LHS=RHS

---

https://en.wikipedia.org/wiki/Vandermonde's_identity#Combinatorial_proof
this is the best i could find

---

I have not found any proof which is purely algebraic (apart from the binomial theorem one, which is pretty close). Please see if any of these links help,
https://math.stackexchange.com/questions/219928/inductive-proof-for-vandermondes-identity/219938 

https://www.cut-the-knot.org/arithmetic/algebra/VandermondeConvolution.shtml