3
$\begingroup$

How can i prove that : $$\binom{n}{0}^2+\binom{n}{1}^2+\binom{n}{2}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}$$

i tried to prove it : by

$$\binom{2n}{n} = \frac{(2n)!}{n!n!} = \frac{2^n (1\cdot3\cdot5\cdots(2n-1))}{n!}$$

but i can’t take advantage of it.

$\endgroup$
2
  • 2
    $\begingroup$ Note that in English, "prove" is a verb and "proof" is a noun. The vowel sounds the same in both words. I edited the question accordingly. It is one of a number of instances of a word being a noun when it ends with a voiceless consonant and a verb when it ends with the corresponding voiced consonant. Among other examples are "believe" and "belief", "advise" and "advice", and "use" pronounced with a voiced final "s" and "use" pronounced with a voiceless final "s" (similarly with "house"). ${}\qquad{}$ $\endgroup$ – Michael Hardy Mar 6 '15 at 13:23
  • 2
    $\begingroup$ Three answers have been posted so far (incluind mine; see below), and yet I am the only person who has up-voted the question. $\endgroup$ – Michael Hardy Mar 6 '15 at 13:32
9
$\begingroup$

Consider the coefficient of $x^n$ in the expansion of $$(1+x)^n(x+1)^n=(1+x)^{2n},$$ i.e. $$\left(\binom{n}{0}x^n+\binom{n}{1}x^{n-1}+\cdots+\binom{n}{n}x^0\right)\left(\binom{n}{0}x^0+\binom{n}{1}x^1+\cdots+\binom{n}{n}x^n\right)$$ $$=\binom{2n}{0}x^{2n}+\binom{2n}{1}x^{2n-1}+\cdots+\binom{2n}{2n}x^0.$$

$\endgroup$
2
  • $\begingroup$ I can't help but notice you already have a similar answer here, yet you still chose not to leave any comment or mark this as duplicate. $\endgroup$ – AvZ Mar 6 '15 at 13:49
  • $\begingroup$ @AvZ: To be honest, I forgot writing the answer. Thank you for pointing it out, anyway. $\endgroup$ – mathlove Mar 6 '15 at 15:15
3
$\begingroup$

$$\binom{n}{0}^2+\binom{n}{1}^2+\cdots+\binom{n}{n}^2$$ $$=\binom{n}{0}\binom{n}{n}+\binom{n}{1}\binom{n}{n-1}+\cdots+\binom{n}{n}\binom{n}{0}$$ Note that the above formula denotes the number of ways of picking $n$ objects out of $2n$.
Hence, the answer is $$\binom{2n}{n}$$

$\endgroup$
1
$\begingroup$

${\dbinom n k}^2$ is the same as $\dbinom n k\cdot\dbinom n {n-k}$.

In a committee composed of $n$ men and $n$ women, the number of ways to choose $k$ men and $n-k$ women is that product. Summing from $k=0$ to $k=n$ gives the whole number of ways to choose a subcommittee of $n$ members. The proposed identity follows.

$\endgroup$

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