# $\sum_{k=-m}^{n} \binom{m+k}{r} \binom{n-k}{s} =\binom{m+n+1}{r+s+1}$ using Counting argument

I saw this question here:- Combinatorial sum identity for a choose function

This looks so much like a vandermonde identity, I know we can give a counting argument for Vandermonde. However much I try I am not able to come up with a counting argument for this.

Let $S=\{-m,-m+1,\ldots,n-1,n\}$; $|S|=m+n+1$, and we want to count the subsets of $S$ of cardinality $r+s+1$. Suppose that $A$ is such a subset. Then there is a unique $k_A\in A$ such that $r$ members of $A$ are smaller than $k_A$, and $s$ members of $A$ are larger than $k_A$. Let $\mathscr{A}_k$ be the family of $(r+s+1)$-element subsets $A$ of $S$ such that $k_A=k$. There are $k-(-m)=m+k$ elements of $S$ less than $k$ and $n-k$ elements of $S$ greater than $k$, so

$$|\mathscr{A}_k|=\binom{m+k}r\binom{n-k}s\;.$$

Summing over $k$ gives us the total number of $(r+s+1)$-element subsets of $S$, which is of course $\binom{m+n+1}{r+s+1}$, so

$$\sum_{k=-m}^n\binom{m+k}r\binom{n-k}s=\binom{m+n+1}{r+s+1}\;.$$

• Could you clarify this "there are k-(-m)=m+k elements of S less than k and n-k elements greater than k " ? Here k is just a element of A right? – Amrita Sep 23 '16 at 19:27
• @Amrita: $k$ is a potential element of some $A$, so it can be any element of $S$. Since $-m$ is the smallest element of $S$, there are $k-(-m)$ elements of $S$ smaller than $k$. Similarly, since $n$ is the largest element of $S$, there are $n-k$ elements of $S$ larger than $k$. I use that information to count the sets $A\subseteq S$ such that $|A|=r+s+1$, $k\in A$, and $A$ has exactly $r$ of its elements less than $k$. – Brian M. Scott Sep 23 '16 at 19:32
• Wow! you came up with this in 20 mins. I have been trying that question since it was posted. I would be very interested in knowing how you started and approach such a question. – Amrita Sep 23 '16 at 19:41
• @Amrita: As you said in the question, it strongly resembles Vandermonde’s identity, so I looked for a combinatorial argument similar to the one for that identity. The terms in the summation are clearly choosing $r$ members of one set and $s$ of another, and the righthand side is clearly counting sets of size $r+s+1$, so experience tells me that there’s a good chance that the lefthand side is counting sets categorized by their $(r+1)$-st member, the one with $r$ elements below it and $s$ above. Then it was just a matter of checking that $m+k$ and $n-k$ fit that interpretation. – Brian M. Scott Sep 23 '16 at 19:46
• @Sarah: List the $r+s+1$ elements of $A$ from smallest to largest; the $(r+1)$-st element in that list is the only member of $A$ that is larger than $r$ members of $A$ and smaller than $s$ members of $A$. – Brian M. Scott Sep 28 '16 at 21:29

You have $$m+n+2$$ identical coins, and $$r+s+2$$ distinct boxes.
How many ways are there to place all the coins in the boxes so no box is empty?

If you place these $$m+n+2$$ coins in a line, then there are $$m+n+1$$ spaces between pairs of adjacent coins, and we can choose $$r+s+1$$ of these spaces to place a divider in. These dividers split the row of coins into $$r+s+2$$ contiguous blocks, representing the $$r+s+2$$ boxes, and therefore uniquely describing a placement of coins in boxes. Therefore, the number of ways to place the coins is $$\binom{m+n+2}{r+s+1}$$.

On the other hand, we can instead count how many ways to place the coins there are where the first $$r+1$$ boxes receive $$m+k+1$$ coins total, meaning the remaining $$s+1$$ boxes receive the remaining $$n-k+1$$ coins, and then sum over $$k$$. By the same argument, there are $$\binom{m+k}r$$ ways to place the $$m+k+1$$ coins in the first $$r+1$$ boxes, and $$\binom{n-k}{s}$$ ways to place the remaining $$n-k+1$$ coins in the other $$s+1$$ boxes.