Vandermonde's ConvolutionDate: 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. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/