Permutation and Combination Equality

Date: 07/18/99 at 02:30:10
From: Carlos H. Griese Neto
Subject: Proof of a Permutation and Combination Equality

Prove that

(nC0)^2 + (nC1)^2 + (nC2)^2 + ... + (nCn)^2 = (2nCn)

where nCi = n!/((n-i)!*i!)

Date: 07/18/99 at 08:43:42
From: Doctor Floor
Subject: Re: Proof of a Permutation and Combination Equality

For your problem, we will consider a rhombus from Pascal's triangle:

                1
              1   1
          ...       ...
      ...              ...
C(n, 0)  C(n, 1) ... C(n, n - 1) C(n, n)
      ...              ...
          ...        ...
       C(2n - 1,  n - 1)  C(2n - 1,  n)
              C(2n, n)

We can consider C(2n, n) as a combination of values from the nth row 
in Pascal's triangle. Each entry in the nth row has to be counted for 
the number of routes that there are from that entry to C(2n, n). For 
instance, C(n, 0) has to be counted once, because there is only one 
route from C(n, 0) to C(2n, n) in Pascal's triangle. And C(n, 1) has 
to be counted n times, because there are n routes from C(n, 1) to 
C(2n, n). 

In general, we can see, from the symmetry of the rhombus we have made, 
that the number of routes from C(n, m) to C(2n, n), for any m, is the 
same as the number of routes from C(0, 0) (the top) to C(n, m). But 
the number of routes from C(0, 0) to C(n, m) is equal to C(n, m). So, 
C(n, m) has to be counted C(n, m) times.

And we find,

 C(2n, n) = C(n, 0)^2 + C(n, 1)^2 + ... + C(n, n)^2, 

as desired.

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/