Proof of Chu–Vandermonde identity

Question

I am working through Probability Theory, the logic of Science by E.T. Jaynes and came across the following equation (6.16):

$$S \equiv \sum_{R=0}^N {R \choose r} {N - R \choose n - r} = {N + 1 \choose n + 1}$$

I have been trying to find a proof for this and came across the Chu–Vandermonde identity on wikipedia (eq. 9), which can take the form:

$$ \sum_{m=0}^n {m \choose j} {n - m \choose k - j} = {n + 1 \choose k + 1} $$

It looks like this is the identity that I need, but I have not been able to find a proof of this particular form and was hoping someone may be able to point me to it, or help me walk through it. Thanks!

Answer 1

$\binom{n+1}{k+1}$ counts the number of $(k+1)$-element subsets of the set $S=\{1,2,\ldots,n+1\}$. Let us count the number of these subsets whose $(j+1)$-th smallest element is $m+1$. Such a set contains, apart from $m+1$, $j$ elements from the set $\{1,\ldots,m\}$ and $k-j$ elements from $\{m+2,\ldots,n+1\}$. There are $\binom mj\binom{n-m}{k-j}$ such subsets. Adding up over all admissible values of $m$ gives the result.

Answer 2

Let $0\leq j\leq k\le n$. Suppose we want to choose $k$ items from a group of $n+1$ standing in a line. Determine an $m$ so that the $j+1$st item chosen is the $m+1$st item it the line. Then choose $j$ of the first $m$ items and $k-j$ of the last $n-m$ items.

Answer 3

Wikipedia has a short sentence explaining. Let me elaborate on it a bit further.

Consider the polynomial $(1+x)^m(1+x)^{n-m}=(1+x)^n$. Let's say we want to find the coefficient of a term $x^k$. We could do this by expanding the factors on the LHS and then adding the products of the coefficients that contribute to this term. This would give us $$\sum_{j=0}^k \binom{m}{j}\binom{n-m}{k-j},$$ by the Binomial Theorem.

Alternatively, we could use the Binomial Theorem directly on the RHS, to obtain $\binom{n}{k}.$ Since we're counting the same thing, our conclusion is that these two must be equal.

EDIT: As @LordSharktheUnknown points out, the equation you’re asking about is slightly different. However, by considering the equation $(1+x)^{-j-1}(1+x)^{-k+j-1}=(1+x)^{-k-2}$, and taking the factors on the left side as formal power series, one can obtain Vandermonde’s other formulation.