Can this be proved using Combinatorics or generating functions?
Solution 1:
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}.$
Solution 2:
Using coefficient extractors we get for the LHS
$$\sum_{r=0}^n {n\choose r} {m+r\choose n} = [z^n] (1+z)^m \sum_{r=0}^n {n\choose r} (1+z)^r = [z^n] (1+z)^m (2+z)^n.$$
We get for the RHS
$$\sum_{r=0}^n {n\choose r} {m\choose r} 2^r = \sum_{r=0}^n {n\choose r} {m\choose m-r} 2^r \\ = [z^m] (1+z)^m \sum_{r=0}^n {n\choose r} 2^r z^r = [z^m] (1+z)^m (1+2z)^n.$$
This last term is
$$\mathrm{Res}_{z=0} \frac{1}{z^{m+1}} (1+z)^m (1+2z)^n.$$
There is no pole other than the one at zero and residues sum to zero so this is
$$-\mathrm{Res}_{z=\infty} \frac{1}{z^{m+1}} (1+z)^m (1+2z)^n \\ = \mathrm{Res}_{z=0} \frac{1}{z^2} z^{m+1} \frac{(1+z)^m}{z^m} \frac{(2+z)^n}{z^n} \\ = \mathrm{Res}_{z=0} \frac{1}{z^{n+1}} (1+z)^m (2+z)^n = [z^n] (1+z)^m (2+z)^n.$$
This is the claim.
Solution 3:
This is another version of Phicar’s solution.
There are $n$ students and $m$ professionals. All professionals are member of chess club while students can be in the club or not. Suppose that we want to choose $n$ people from the club’s members to join a competition.
In the LHS, $r$ students are in chess club, $\binom{n}{r}$. Therefore, there are $m+r$ chess club members to choose from, $\binom{m+r}{n}$. Hence $\sum_{r=0}^{n}{\binom{n}{r}\binom{m+r}{n}}$
In the RHS, $r$ professionals join the competition, $\binom{m}{r}$. Therefore, $n-r$ students must be members of the club and join the competition, $\binom{n}{n-r}=\binom{n}{r}$. The remaining $r$ students can be in the club or not, $2^{r}$. Hence $\sum_{r=0}^{n}{\binom{n}{r}\binom{m}{r}2^{r}}$
Solution 4:
$$ \eqalign{ & \sum\limits_{\left( {0\, \le } \right)\,r\,\left( { \le \,n} \right)} {\left( \matrix{ n \cr r \cr} \right)\left( \matrix{ m + r \cr n \cr} \right)} = \sum\limits_{\left( {0\, \le } \right)\,r\,\left( { \le \,n} \right)} {\left( \matrix{ n \cr r \cr} \right)\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( \matrix{ r \cr k \cr} \right)\left( \matrix{ m \cr n - k \cr} \right)} } = \cr & = \sum\limits_k {\sum\limits_r {\left( \matrix{ m \cr n - k \cr} \right)\left( \matrix{ n \cr r \cr} \right)\left( \matrix{ r \cr k \cr} \right)} } = \sum\limits_k {\sum\limits_r {\left( \matrix{ m \cr n - k \cr} \right)\left( \matrix{ n \cr k \cr} \right)\left( \matrix{ n - k \cr r - k \cr} \right)} } = \cr & = \sum\limits_k {\sum\limits_r {\left( \matrix{ m \cr n - k \cr} \right)\left( \matrix{ n \cr k \cr} \right)\left( \matrix{ n - k \cr n - r \cr} \right)} } = \sum\limits_k {\left( \matrix{ m \cr n - k \cr} \right)\left( \matrix{ n \cr k \cr} \right)2^{n - k} } = \cr & = \sum\limits_k {\left( \matrix{ m \cr k \cr} \right)\left( \matrix{ n \cr k \cr} \right)2^k } \cr} $$
Note that the sum bounds put in parenthesis is to indicate that they can be omitted since they are implicit in the binomial(s), i.e. the binomials are null outside of the bounds.
Then the steps are:
- expand 2nd b. as Vandermonde's Convolution;
- group and invert the summation indices;
- apply the "trinomial revision" identity on last two b. $$ \eqalign{ & \left( \matrix{ n \cr r \cr} \right)\left( \matrix{ r \cr k \cr} \right) = {{n!} \over {r!\left( {n - r} \right)!}}{{r!} \over {k!\left( {r - k} \right)!}} = {{n!} \over {\left( {n - r} \right)!k!\left( {r - k} \right)!}} = \cr & {{n!} \over {\left( {n - k} \right)!k!}}{{\left( {n - k} \right)!} \over {\left( {n - r} \right)!\left( {r - k} \right)!}} = \left( \matrix{ n \cr k \cr} \right)\left( \matrix{ n - k \cr r - k \cr} \right) \cr} $$
- sum on r, and change $n-k$ with $k$