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.

How to prove $\forall n \in \mathbb N$

$$\sum_{m = 0}^{n} \left(\frac{n!}{m!(n-m)!}\right)^2=\frac{(2n)!}{(n!)^2}$$

share|improve this question
1  
think about this, divide $2n$ balls into two equal piles of balls with $n$ for each. And you are going to take $n$ balls from them. –  Yimin Feb 24 '13 at 17:36
    
It's just $\sum_{m = 0}^{n} (C_m^n)^2$ –  hjpotter92 Feb 24 '13 at 17:37
    
@BackinaFlash it is $C_n^m$ –  Yimin Feb 24 '13 at 17:37
    
@Yimin Last time I checked, there was a square too; and $n!$ is numerator. –  hjpotter92 Feb 24 '13 at 17:38
add comment

3 Answers 3

up vote 3 down vote accepted

In terms of binomial coefficients the proposed identity is

$$\sum_{m=0}^n\binom{n}m^2=\binom{2n}n\;.$$

Once you realize that $\dbinom{n}m^2=\dbinom{n}m\dbinom{n}{n-m}$, this becomes a special case of Vandermonde’s identity, and you’ll find a combinatorial proof in the linked article. (I’m pretty sure that you’ll also find combinatorial proofs on this site.)

share|improve this answer
1  
You mean $$\sum_{m=0}^n\binom{n}m^2$$ –  hjpotter92 Feb 24 '13 at 17:42
    
@BackinaFlash: And $n$ on top everwhere else, too. Thanks. –  Brian M. Scott Feb 24 '13 at 17:44
    
@Maisam: You’re welcome. –  Brian M. Scott Feb 24 '13 at 17:46
add comment

Note that $$\left(\frac{n!}{m!(n-m)!}\right)^2=\binom{n}{m}\binom{n}{n-m}.$$ Now imagine that we have a group of $n$ boys and $n$ girls, and want to choose a committee of $n$ people.

It is clear that the number of ways to choose a committee of $n$ from our $2n$ people is $\binom{2n}{n}=\frac{(2n)!}{n!n!}$.

Now let us count this another way. For any $m$ with $0\le m\le n$, there are $\binom{n}{m}\binom{n}{n-m}$ ways to choose a committee with $m$ boys and $n-m$ grls. Sum over all $m$.

Remark: Counting something in two different ways can be a powerful method for proving combinatorial identities.

share|improve this answer
add comment

First of all $$ \frac{n!}{m!(n-m)!} = \binom{n}{m} $$ is a binomial coefficient, and so is $$ \frac{(2n)!}{(n!)^2} = \binom{2n}{n} $$

Then consider the coefficient of $x^{n}$ in $$ (1 + x)^{2n}, $$ which is $\dbinom{2n}{n}$, but can also be computed via $$ (1 + x)^{2n} = ((1 + x)^{n})^{2} = (\sum_{m=0}^{n} \binom{n}{m} x^{m})^{2} $$ as $$ \sum_{m = 0}^{n} \binom{n}{m} \binom{n}{n-m} = \sum_{m = 0}^{n} \binom{n}{m}^{2} $$

share|improve this answer
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.