# How to get ${n \choose 0}^2+{n \choose 1}^2+{n \choose 2}^2+\cdots+{n \choose n}^2 = {x \choose y}$

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.

## 3 Answers

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$$

• This is completely clear, thank you so much :D – Jake Timberwood May 28 '13 at 13:00
• You're welcome:) – user63181 May 28 '13 at 13:00
• Excellent answer, Sami! – 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$.

• It takes me so long to interpret this, but thank you – Jake Timberwood May 28 '13 at 13:04
• 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$) – 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.

• 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? – Jake Timberwood May 28 '13 at 12:58
• @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. – J. J. May 28 '13 at 13:01
• yes, his explanation could clearly be understood, however thank you for the explanation :) – Jake Timberwood May 28 '13 at 13:07