I have a question with regards to combinatorics. I am supposed to show the following combinatorial identity: $\sum\limits_{r=0}^n\binom{n}{r}\binom{m+r}{n}=\sum\limits_{r=0}^n\binom{n}{r}\binom{m}{r}2^r$.
The algebraic way is to consider the coefficient of $t^m$ in the expansion of $(1+t)^n(1-t)^{-(n+1)}$. For $r\in\{0,1,\cdots,n\}$, we have the coefficient of $t^{n-r}$ in the expansion of $(1+t)^n$ to be equal to $\binom{n}{r}$, and the coefficient of $t^{m+r-n}$ in the expansion of $(1-t)^{-(n+1)}$ to be equal to $\binom{m+r}{n}$. By the addition and multiplication principles this will show that the coefficient of $t^m$ in the expansion of $(1+t)^n(1-t)^{-(n+1)}$ will be equal to $\sum\limits_{r=0}^n\binom{n}{r}\binom{m+r}{n}$.
On the other hand, we note that $(1+t)^n(1-t)^{-(n+1)}=(1+\frac{2t}{1-t})^n(1-t)^{-1}=\sum\limits_{r=0}^n\binom{n}{r}2^rt^r(1-t)^{-(r+1)}$. As the coefficient of $t^{m-r}$ is equal to $\binom{m}{r}$, this implies that the coefficient of $t^m$ in the expansion of $(1+t)^n(1-t)^{-(n+1)}$ is equal to $\sum\limits_{r=0}^n\binom{n}{r}\binom{m}{r}2^r$.
What I am thinking of, is to think of a way to prove this identity without the use of the generalized binomial series. I was trying to think of a combinatorial method to solve this problem. In particular, I was trying to prove the combinatorial identity as follows:
Firstly, let us be given a class of $n$ boys and a class of $m$ girls, where $n\leq m$. Choose a team $A$ of $r$ boys, and choose a team $B$ of $r$ girls, and finally choose any subset (may be empty) of boys from $A$ to clean the classroom, where $r\in\{0,1,\cdots,n\}$. For each value of $r$, we see that there are $\binom{n}{r}$ choices for $A$, $\binom{m}{r}$ choices for $B$, and subsequently there are $2^r$ ways to choose a subset from $A$. In this way we get the number of ways to do so to be equal to the expression on the RHS of the identity.
What I am struggling though, is to be able to count the number of desired ways in a way that will give me the expression on the LHS of the identity. I tried firstly to choose the boys to clean the classroom before choosing the sets $A$ and $B$, but I wound up with some messy expression that does not seem close to matching the expression on the LHS.
I would like to know if there is another way of looking at this method (or I could have been missing out on something), or if there is any other combinatorial method (or any other algebraic method that does not involve the use of generalized binomial series) that one could think of to show the desired identity.
Best Answer
An approach using common binomial identities: $$ \begin{align} \sum_{r=0}^n\binom{n}{r}\binom{m+r}{n} &=\sum_{r=0}^n\binom{n}{r}\sum_{k=0}^n\binom{m}{k}\binom{r}{n-k}\tag{1}\\ &=\sum_{k=0}^n\binom{m}{k}\sum_{r=0}^n\binom{n}{r}\binom{r}{n-k}\tag{2}\\ &=\sum_{k=0}^n\binom{m}{k}\sum_{r=0}^n\binom{n}{n-k}\binom{k}{r-n+k}\tag{3}\\ &=\sum_{k=0}^n\binom{m}{k}\binom{n}{k}2^k\tag{4} \end{align} $$ Explanation:
$(1)$: $\sum\limits_{k=0}^n\binom{m}{k}\binom{r}{n-k}=\binom{m+r}{n}$
$(2)$: change order of summation
$(3)$: $\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}$
$(4)$: $\sum\limits_{k=0}^n\binom{n}{k}=2^n$