Prove that if $n\geq1$ then $$\binom{2n}{n}=\sum_{k=0}^{n}(\binom{n}{k})^2$$

This is what I have so far:

By the Binomial Theorem: $$\binom{2n}{n}=\frac{(2n)!}{(2n-2)!n!}=\frac{2n!~}{n^2(n-1)^2(n-2)^2...1}$$

By the definition of summation: $$\sum_{k=0}^{n}(\binom{n}{k})^2=(\binom{n}{0})^2+(\binom{n}{1})^2+(\binom{n}{2})^2+(\binom{n}{3})^2+...+(\binom{n}{n})^2$$

By the Binomial Theorem => $$\sum_{k=0}^{n}(\binom{n}{k})^2=1^2+(\frac{n!}{(n-1)!})^2+(\frac{n!}{(n-2)!2!})^2+(\frac{n!}{(n-3)!3!})^2+...+1^2$$


This is where I get stuck. I'm not sure how to continue from here. I know that what I am getting is starting to look a lot like what I want it to look like but I don't know how to finish, nor am I sure that I've done it correctly to this point. Help?


marked as duplicate by Jack D'Aurizio, Chappers, user940, Austin Mohr, Lucian Sep 24 '15 at 15:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Hint: $(1+x)^n(1+x)^n = (1+x)^{2n}$ and $\binom{n}{k} = \binom{n}{n-k}$. $\endgroup$ – Dilip Sarwate Sep 24 '15 at 14:16
  • $\begingroup$ Use $\displaystyle{a\choose b}={a\choose a-b}$ and Vandermonde's identity. $\endgroup$ – Lucian Sep 24 '15 at 15:07

Although this question has been answered, I have another proof.

Let $N=\{1,\ldots,n\}$, $N_2=\{1,2\}\times N$, $A$ be the set of subsets of $N$, $B=\{(X,Y)\in A\times A:|X|=|Y|\}$ and $C=\{X\subset N_2:|X|=n\}$.

It's easy to show that $$|B|=\sum_{k=0}^n\binom nk^2$$ and $$|C|=\binom {2n}n$$ Therefore, our goal is to show that $|B|=|C|$, so let's build a bijective function from $C$ to $B$.

Let be $X\subset N_2$. $X$ has $k$ elements whose first component is $1$ and $n-k$ elements whose first component is $2$. Define $$f(X)=\Big(\{v:(1,v)\in X\},\{v:(2,v)\notin X\}\Big)$$ Since $f$ is bijective, we are finished.

To say it in plain words, we can render $N_2$ as a matrix like this: $$\begin{pmatrix}1&2&\cdots& n\\1&2&\cdots& n\end{pmatrix}$$ Choosing a set $X\subset C$ is choosing $n$ terms of the matrix. This leaves $k$ terms selected in the first row and $k$ terms unselected in the second row. This is like selecting two subsets of the sime size from $N$, which is like selecting an element from $B$.


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