Associated Topics || Dr. Math Home || Search Dr. Math

### Vandermonde's Convolution

```Date: 05/23/2002 at 07:00:14
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

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
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
Subject: Inductive proof

Thanks alot for the proof.  As usual, things look so "easy" with the
solution in front of you.
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search