Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can you guys help me prove this? There is a way of proving this logically but I was hoping to find a more "mathematical" proof, if possible.

$$\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$$

Logical Proof:

$${n \choose k}^2 = {n \choose k}{ n \choose n-k}$$

Hence summation can be expressed as:

$$\binom{n}{0}\binom{n}{n} + \binom{n}{1}\binom{n}{n-1} + \cdots + \binom{n}{n}\binom{n}{0}$$

One can think of it as choosing $n$ people from a group of $2n$ (imagine dividing a group of $2n$ into $2$ groups of $n$ people each. I can get $k$ people from group $1$ and another $n-k$ people from group $2$. We do this from $k = 0$ to $n$)

share|improve this question
6  
Just FYI, what you call a "logical proof" is known as a "combinatorial proof", and such a proof is perfectly valid and often very insightful. What I suspect you mean by "mathematical proof" is one dealing with the numerical structure of sums and combinations, which would be better called an "analytical proof". Both styles of proof are equally mathematical. –  Austin Mohr May 23 '12 at 4:57
3  
This is secretly subsumed by this question –  mixedmath May 23 '12 at 5:00
1  
You could obtain the same combinatorial proof by noting that $\binom{2n}{n}$ counts the number of paths from $(0,0)$ to $(n,n)$ on an $n\times n$ grid. –  Holdsworth88 May 23 '12 at 6:03
4  
I think your combinatorial proof is really nice, and you should not be unhappy with it. –  MJD May 23 '12 at 13:54
1  
Incidentally, this is a special case of math.stackexchange.com/questions/337923/…. –  LePressentiment Nov 16 '13 at 10:26
show 1 more comment

1 Answer 1

The combinatorial explanation is straightforward. There's also a roundabout approach through what are called "generating functions." The binomial theorem tells us that

$$(1+x)^n(x+1)^n=\left(\sum_{a=0}^n\binom{n}{a}x^a\right)\left(\sum_{b=0}^n\binom{n}{b}x^{n-b}\right)=\sum_{c=0}^{2n}\left(\sum_{a+n-b=c}\binom{n}{a}\binom{n}{b}\right)x^c$$

The $x^n$ coefficient of the above occurs with $c=n$, wherein the coefficient is

$$\sum_{a+n-b=n}\binom{n}{a}\binom{n}{b}=\sum_{a=0}^n\binom{n}{a}^2.$$

However, the $x^n$ coefficient of $(1+x)^n(x+1)^n=(1+x)^{2n}$, again by the binomial theorem, is

$$\binom{2n}{n}. $$

Equating the two gives the result.

share|improve this answer
    
+1. @Lance C Do you see that this is the same as your "logical" proof? Choosing $n$ people from $2n$ is what you are doing when you look at the coefficient of $x^n$ in the expansion. –  user17762 May 23 '12 at 5:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.