Vandermonde's Convolution

Date: 05/23/2002 at 07:00:14
From: Brad Jorgenson
Subject: Inductive proof

I am trying to prove that 

 (nC0)^2 + (nC1)^2 +... + (nCn)^2 = (2n)!/(n!)^2

I substituted k for n and then k+1 for k and tried to 
simplify both sides of the equation.  I thought a whole bunch of 
terms would cancel out but every step I turn it leads to a dead end.  
I have tried for 5 hours and can't find an answer.

A preemptive thank you.

Date: 05/23/2002 at 08:43:16
From: Doctor Pete
Subject: Re: Inductive proof

Hi Brad,

The particular identity you are trying to prove is in fact a special 
case of Vandermonde's convolution, discussed by Alexandre Vandermonde 
in the late 18th century. (But interestingly, it was known by the 
Chinese mathematician Chu Shih-Chieh as early as 1303!)  The 
Vandermonde convolution states that

     Sum[Binomial[r,k] * Binomial[s,n-k], k] = Binomial[r+s,n],

where Binomial[n,k] = n!/(k!(n-k)!) is the binomial coefficient or 
number of ways to choose a subset of k objects from a set of n 
distinguishable objects.  The sum on the left-hand side is taken over 
all integers k, with the convention that

     Binomial[n,k] = 0,  if k < 0, or k > n.

If we take r = s = n in Vandermonde's convolution, and make the 
observation that

     Binomial[n,k] = Binomial[n-k],

we obtain

     Sum[Binomial[n,k]^2, k] = Binomial[2n,n],

which is equivalent to your identity.

At this point I have to say that I do not know of a proof of your 
original identity that uses induction.  It must rely on significant 
computation, because clearly the right-hand side for the case n+1 
gives

     Binomial[2(n+1), n+1] = (2n+2)(2n+1)(2n!)/((n+1)^2(n!n!))

                           = (2(2n+1)/(n+1)) Binomial[2n,n],

and so the expression of the next case as a function of the previous 
is somewhat complicated.

However, the good news is that Vandermonde's convolution has several 
direct proofs, and thus your desired result will follow as a 
corollary.

The first proof I will give is combinatorial.  Suppose we have a 
group of people consisting of r men, and s women.  Then the right-
hand side of the convolution, Binomial[r+s,n] counts the number of 
ways to choose n people from this group.

To represent the left-hand side of the convolution, we count the 
people a different way.  For each k between 0 and n, we choose k men 
and n-k women.  Thus the total number of ways to do this is

     Binomial[r,k] * Binomial[s,n-k].

(What happens if r < k or s < n-k, and how does this correspond to 
the interpretation of these binomial coefficients as ways of choosing 
people in a group?)

If we sum the above expression from k = 0 to k = n, we then clearly 
obtain the total number of ways of choosing n people from a group of 
r+s people (we have not counted any choice twice, because each value 
of k is distinct).  This is the same as the right-hand side, and 
therefore the result is proven.

If you don't really like this proof, I can give another one, which 
involves what are called generating functions.

Consider the formal (i.e., without regard to convergence) power series

     A[z] = Sum[a[k]z^k, k >= 0]

generated by a sequence of values {a[0],a[1],a[2],...}.  If we have 
two such power series A[z] and B[z], then their product looks like

     A[z]B[z] = (a[0]+a[1]z+a[2]z^2+ ...)(b[0]+b[1]z+b[2]z^2+ ...)

              =    a[0]b[0] 
                + (a[0]b[1]+a[1]b[0])z
                + (a[0]b[2]+a[1]b[1]+a[2]b[0])z^2 
                + ...,

and therefore we see that the coefficient of z^n is given by

     a[0]b[n]+a[1]b[n-1]+...+a[n]b[0] = Sum[a[k]b[n-k], 0<=k<=n].

Thus the product of two power series forms a third, which we will 
write C[z] = A[z]B[z], and the sequence of its terms

     c[n] = Sum[a[k]b[n-k], 0<=k<=n]

is called the convolution of the sequences a[n] and b[n].

Now we are ready for the proof.  Recall that the Binomial Theorem 
states

     (1+z)^r = Sum[Binomial[r,k]z^k, k >= 0].

(Here I have made a slight modification, as the upper limit of the 
sum is usually r, but since Binomial[r,k] = 0 if k > r, we can just 
sum over all nonnegative integers k.)

Thus, consider what happens if we take the product of two such power 
series; e.g.,

     (1+z)^r (1+z)^s

   = Sum[Binomial[r,k]z^k, k >= 0]*Sum[Binomial[s,k]z^k, k >= 0]

   = Sum[c[n]z^n, n >= 0],

where

     c[n] = Sum[Binomial[r,k]Binomial[s,n-k], 0<=k<=n].

This much is clear from our previous discussion of the convolution of 
the coefficients of two power series.  But we also have

     (1+z)^r (1+z)^s = (1+z)^(r+s)

                     = Sum[Binomial[r+s,n]z^n, n >= 0],

this time directly from the Binomial Theorem.  By equating the 
coefficients of z^n of these power series, we again obtain 
Vandermonde's convolution.  In fact, it is by this method of proof 
that we understand the name for this particular identity.

In actuality, both of the proofs I supplied are the very simple 
application of very sophisticated ideas; the first proof relying on 
an elegant and inspired interpretation of the identity as two 
different enumerations of combinatorial objects, and the second 
relying on the powerful technique of generating functions.

I know you asked for a proof of a special case by induction, and I 
apologize if that's really what you need - I will give it some more 
thought and see what I can come up with.  Still, I wanted to show you 
a little bit of how such things can be generalized and proven in 
interesting and instructive ways.


- Doctor Pete, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 05/23/2002 at 08:59:38
From: Brad Jorgenson
Subject: Inductive proof

Thanks alot for the proof.  As usual, things look so "easy" with the 
solution in front of you.