What is the proof for this identity?
$\displaystyle\sum_{r=0}^{n}\binom{n}{r}\binom{m+r}{n}\ = \displaystyle\sum_{r=0}^{n}\binom{n}{r}\binom{m}{r}2^{r}$
I thought of changing $r$ to $n-r$ on left and right both. Then, I thought of building a set with atleast $n$ elements and atmost $2n$ elements with atmost $n$ elements from $m$ element set, and we can do this on LHS by choosing $n-r$ elements from n and out of remaining $r+m$ elements we can choose n more elements. On RHS, we can again choose $n-r$ elements from $n$ and $r$ elements from $m$, then remaining $r$ elements from n element set have 2 choices each. But I think it has a flaw. Can someone please help? If my proof is not correct, please suggest a combinatorial or a generating function proof.
Best Answer
The story would be like(any resemblance to reality is pure coincidence) :
Suppose you want to build a committee of $n$ mathematicians. You have a pool of $n$ graduate students and $m$ full professors. The rule is that you have to double vote the graduate students. That means, first you choose the graduate students(first filter) and then you choose from the pool of professors and selected graduate students(second filter).
The LHS is you choose $r$ graduate students and then you choose from $m+r$ candidates, the $n$ mathematicians.
The right hand side is you choose the amount of professors that are going to be in the final committee, say $r,$ in $\binom{m}{r}$ and so there should be $n-r$ graduate students. You choose them in $\binom{n}{n-r}$ but notice that the remaining $r$ graduate students, perhaps, pass the first filter so you are going to mark the ones that pass the first filter, you can do that in $2^r$ ways.
This should be reminescent of the proof of $\binom{a}{b}\binom{b}{c}=\binom{a}{c}\binom{a-c}{b-c}.$