Is there a simple combinatorial proof for the following identity?

$$\sum_{0\leq i \leq m} \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$$ where $m,j \geq 0$, $k \geq n \geq 0$.


Count $(j+k+1)$ element subsets of an ordered set with ($m+n+1$) elements, organizing the subsets by the value of the $(j+1)$-th largest element in the subset. The product of two binomial coefficients on the left side of the equation is the number of ways to choose the rest of the subset when the $(j+1)$-th largest elements in the subset is the $(m-i)$-th largest element in the whole set.

I think this formula is called the dual Vandermonde or negative Vandermonde identity.

Edit. The inequality between $n$ and $k$ in the question has the wrong sign, it should be $n \leq k$.

  • $\begingroup$ Thanks zyx for your answer and for your note. I appreciate. How do you define "n-th largest element in a subset" including when "n=0"? $\endgroup$ – Mike Mar 10 '13 at 5:50
  • $\begingroup$ There is no need to define "i-th largest element in a finite ordered set" for all i. We know what it means to have a (j+k+1) element subset of an ordered set, and what it means to take the (j+1)-th largest element in that subset, and then we ask what is the rank of that element within the larger set. $\endgroup$ – zyx Mar 10 '13 at 7:08
  • $\begingroup$ It looks to me like the formula requires $n \leq k$, which is the opposite of the inequality written in the question. This forces the $j$ element set to be selected from a set of $m$ or fewer (explaining the $m-i$). $\endgroup$ – zyx Mar 10 '13 at 7:22
  • $\begingroup$ @xyz:Thanks.yes, k should be greater or equal n. $\endgroup$ – Mike Mar 10 '13 at 15:15

(Essentially the same as the above)
Counting the number of lattice paths of length l+j+k+1 from $(0,0)$ to $(j+k+1,l)$ with steps $(0,1)$ and $(1,0)$ in two ways, we can derive this identity. Each path includes $(j,s)$ to $(j+1,s)$ step $(s=0,1\ldots l)$.In this way, we can divide paths into l+1 groups which are mutually exclusive. Hence,
$\sum_{0\leq s \leq l} \binom{s+j}{j}\binom{l-s+k}{k} =\binom{l+j+k+1}{l}$
Setting $l=m+n-(j+k)$, $s=(m-j-i)$, we have the identity in question.

  • $\begingroup$ What's the need of adding an answer which is the same as an accepted one on a two years old question? $\endgroup$ – Silvia Ghinassi Nov 28 '15 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.