I found this in my test book, any hints? Given $${n \choose 0}^2+{n \choose 1}^2+{n \choose 2}^2+\cdots+{n \choose n}^2 = {x \choose y}$$ Then find the value of x and y in n. According to the answer provided on last pages of that book, it's $2n \choose n$. What i dont understand is how to get the answer (there's no explanation written there). All i said is thank you so much for every activity to me and i'm sorry for my bad english (english is not my native language) and my messy post.


Let $E=\{a_1,\ldots a_n,b_1,\ldots,b_n\}$ a set with $2n$ elements. There's $2n\choose n$ subsets of $E$ with $n$ elements: $k$ elements from $\{a_1,\ldots,a_n\}$ and $n-k$ elements from $\{b_1,\ldots,b_n\}$ for some $k=0,\ldots,n$ hence we have $${2n\choose n}=\sum_{k=0}^n{n\choose k}{n\choose n-k}=\sum_{k=0}^n{n\choose k}^2$$

  • $\begingroup$ This is completely clear, thank you so much :D $\endgroup$ – Jake Timberwood May 28 '13 at 13:00
  • $\begingroup$ You're welcome:) $\endgroup$ – user63181 May 28 '13 at 13:00
  • $\begingroup$ Excellent answer, Sami! $\endgroup$ – Namaste Jul 4 '14 at 12:09

Hint: compare the coefficient of $x^n$ on both sides of $(1+x)^{2n} = ((1+x)^n))^2$.

  • $\begingroup$ It takes me so long to interpret this, but thank you $\endgroup$ – Jake Timberwood May 28 '13 at 13:04
  • $\begingroup$ I prefer this one as it more easily lends itself to generalisation (i.e. $\binom{n}{0}^k+...+\binom{n}{n}^k$ for general $k$) $\endgroup$ – Meow May 31 '13 at 10:32

Hint: Write it as $${n \choose 0} {n \choose n} + {n \choose 1} {n \choose n-1} + \dots + {n \choose n} {n \choose 0},$$ and use the obvious combinatorial bijection.

  • $\begingroup$ Sorry, i still don't get it, i could only see that if we sum up every term with itself, it will result $2n \choose n$, is it related with the hint you explained? $\endgroup$ – Jake Timberwood May 28 '13 at 12:58
  • $\begingroup$ @Jake Timberwood: Sami Ben Romdhane wrote a full solution. The idea is that you divide the set of $2n$ balls in the first $n$ balls and last $n$ balls. Then you want to choose $n$ balls from them, giving ${2n \choose n}$ ways. But you can also choose first how many balls to choose from the first $n$ balls, say $j$, and then you'll get ${n \choose j}{n \choose n-j}$ possible arrangements. Summing over $j$ and noticing that ${n \choose n-j} = {n \choose j}$, you get the result. $\endgroup$ – J. J. May 28 '13 at 13:01
  • $\begingroup$ yes, his explanation could clearly be understood, however thank you for the explanation :) $\endgroup$ – Jake Timberwood May 28 '13 at 13:07

Your Answer

