# How to prove $\sum\limits_{k\mathop=0}^n\binom nk\cdot\sum\limits_{k\mathop=0}^n\binom nk=\sum\limits_{k\mathop=0}^n\binom{2n}k$

I need to figure out what could be a suitable combinatoric explanation that fits both sides of the equation and why:

$$\left(\sum_{k\mathop=0}^n\binom nk\right)\cdot\left(\sum_{k\mathop=0}^n\binom nk\right)=\sum_{k\mathop=0}^n\binom{2n}k$$

• Please double-check your equation. – Kenny Lau Aug 2 '16 at 8:16
• Indeed there is a problem for the limit of summation in the RHS. – Jean Marie Aug 2 '16 at 8:18

The total number of ways to choose objects from a pile of $2n$ objects

is the same as the total number of ways to choose objects from each of two piles of $n$ objects.

Hint: $((1+x)^n)^2=(1+x)^{2n}$ with $x=1$.

• "combinatoric explanation" – Kenny Lau Aug 2 '16 at 8:19
• All right, my bad.... – Jean Marie Aug 2 '16 at 8:47

Something is wrong with your identity:

Since $\binom{2n}k=\binom{2n}{2n-k}$, we have $$S=\sum_{k\mathop=0}^n\binom{2n}k=\sum_{k\mathop=n}^{2n}\binom{2n}k.$$ Therefore, $$2S=\sum_{k\mathop=0}^{2n}\binom{2n}k 1^k 1^{2n-k}+\binom{2n}n=2^{2n}+\binom{2n}n,$$ $$S=2^{2n-1}+\frac{1}{2}\binom{2n}n$$ where we used binomial formula. On the other hand $$\left(\sum_{k\mathop=0}^n\binom nk\right)\cdot\left(\sum_{k\mathop=0}^n\binom nk\right)=2^n 2^n=2^{2n}.$$ As you can see theese two things are not the same. You probably wanted to show $$\left(\sum_{k\mathop=0}^n\binom nk\right)\cdot\left(\sum_{k\mathop=0}^n\binom nk\right)=\sum_{k\mathop=0}^{2n}\binom{2n}k.$$ This holds since the left side is equal to $2^n 2^n$ and the right side is equal to $2^{2n}$, which goes straightforward by using binomial formula.

• Quote: "a suitable combinatoric explanation". – Did Aug 2 '16 at 9:33
• @Did Sorry, my mistake. Just to point out-there is a typo in equation. – alans Aug 2 '16 at 9:38