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}.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s