# On a combinatorial identity from the paper “Primes in tuples I”

I am reading the seminal paper of Goldston, Pintz, and Yildirim “Primes in tuples I” from the journal Annals of Mathematics (170) (2009). The paper is surprisingly easy to read, and they mention the following identity (it is equation 8.16 in their paper):

$\displaystyle \frac{1}{u!} \sum_{i=0}^u \binom{u}{i} (-1)^i \frac{d(d+1)\cdots(d+i-1)}{(v+d+i)!} = \frac{1}{(u+v+d)!} \binom{u+v}{u}.$

In their paper Goldston, Pintz, and Yildirim state that “it is not hard to prove that [8.16 is true]”. This is indeed the case, but I find the proof itself to be a beautiful and clever application of the famous Chu-Vandermonde identity. So here is the argument I found in detail:

$\displaystyle \frac{1}{u!} \sum_{i=0}^u \binom{u}{i} (-1)^i \frac{d(d+1)\cdots(d+i-1)}{(v+d+i)!}$

$\displaystyle = \frac{1}{u!} \sum_{i=0}^u \binom{u}{i} (-1)^i \frac{(d+i-1)!}{(v+d+i)!(d-1)!}$

$\displaystyle = \sum_{i=0}^u \frac{1}{i!(u-i)!} \frac{(d+i-1)!}{(v+d+i)!(d-1)!}$

$\displaystyle = \frac{1}{(u+v+d)!} \sum_{i=0}^u (-1)^i \frac{(d+i-1)!}{(d-1)! i!} \frac{(u+v+d)!}{(u+v+i)! (u-i)!}$

$\displaystyle = \frac{1}{(u+v+d)!} \sum_{i=0}^u (-1)^i \binom{d+i-1}{i} \binom{u+v+d}{u-i}$

At this point, one recalls the classic Chu-Vandermonde identity, which states that

$\displaystyle \sum_{r=0}^k \binom{n}{r} \binom{m}{k-r} = \binom{m+n}{k}.$

The proof is from the following simple algebraic identity and the binomial theorem:

$(1 + x)^m (1+x)^n = (1+x)^{m+n}.$

However, the binomial theorem is valid (at least formally) for negative exponents as well; and so from the identity

$(1+x)^{u+v+d} (1+x)^{-d} = (1+x)^{u+v}$

we obtain

$\displaystyle \sum_{i=0}^u (-1)^i \binom{d+i-1}{i} \binom{u+v+d}{u-i} = \binom{u+v}{u}.$