# Can this be proved using Combinatorics or generating functions?

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.

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

• Can u elaborate RHS please?@Phicar Nov 25 '20 at 4:40
• Can u please explain how u used $2^{r}$ please?? Nov 25 '20 at 9:31
• There are $r$ students that failed to be in the committee. There are 2 ways to fail for students: did not get the vote at all, or only get 1 vote (recall that students need to be selected twice). Hence $2^{r}$ Nov 25 '20 at 11:37
• Thanks @RezhaAdrianTanuharja , that is precisely it. I see you prefer chess to graduate school.(+1) Nov 25 '20 at 13:10
• @CombatMiners Check Rezha's comment. Let me know if you want me to elaborate further. Nov 25 '20 at 13:11

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.

• Is this proof using generating functions or algebraic or both? Nov 25 '20 at 4:30
• I would say both and formal power series as well. Nov 25 '20 at 15:30

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

• Thank you. I couldn't completely understand Phicar's solution. Your solution made it clear:) Nov 25 '20 at 13:02

\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:

1. expand 2nd b. as Vandermonde's Convolution;
2. group and invert the summation indices;
3. 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}
4. sum on r, and change $$n-k$$ with $$k$$
• what identities are u using in between? I want to know ;_; Nov 25 '20 at 4:35
• Can u explain the identities used here? I mean just write them please:) Nov 25 '20 at 9:41
• @nmnsharma_007: I have explained the steps involved Nov 25 '20 at 12:10
• @CombatMiners: I have explained the steps involved Nov 25 '20 at 12:11
• Thanks a lot!!!!. I really love this platform. U learn a lot of things other than getting your doubt clarified ^_^ Nov 25 '20 at 13:12