How to prove that the sum of squared binomials equals $\binom{2n}{n}$ [duplicate]

This question already has an answer here:

I've stumbled upon this lemma a few times in my textbook: $$\sum_{k=0}^{n}\begin{pmatrix}n\\k\end{pmatrix}^2=\begin{pmatrix}2n\\n\end{pmatrix}$$ I've been trying to prove it, but I simply can't seem to see a connection. I've been trying to use proof by induction, but I can't express the statement for $n+1$ via the statement for $n$.

How do I prove it?

marked as duplicate by user147263, Newb, Chris Janjigian, Thomas, Jonas MeyerDec 27 '14 at 20:10

• You mean $\sum_{k=0}^n\binom{n}{k}^{\color{Red}{2}}=\binom{2n}{n}$? – anon Dec 22 '14 at 19:47
• Please consider changing/editing the title. – Ludolila Dec 22 '14 at 19:48
• – Grigory M Dec 22 '14 at 19:50
• I don't understand the reopen posts. – anon Dec 27 '14 at 19:28
• – Martin Sleziak Dec 16 '15 at 13:39

$${n \choose k} = {n \choose n-k}$$ Then we can divide $2n$ objects into two groups. Form one group we choose $k$ from the other $n-k$ and we assuming all possibilities for $k$. Hence we get: $${2n \choose n}=\sum_{k=0}^n{n \choose k} {n \choose n-k} = \sum_{k=0}^n{n \choose k}^2$$

Since $\dbinom n k= \dbinom n {n-k}$, the identity $$\sum_{k=0}^n \binom n k ^2 = \binom {2n} n$$ is the same as $$\sum_{k=0}^n \binom n k \binom n {n-k} = \binom {2n} n.$$ So say a committee consists of $n$ Democrats and $n$ Republicans, and one will choose a subcommittee of $n$ members. One may choose $k$ Democrats and $n-k$ Republicans in $\dbinom n k \cdot \dbinom n {n-k}$ ways. The number of Democrats is in the set $\{0,1,2,\ldots,n\}$, thus ranging from all Republicans to all Democrats. The sum then gives the total number of ways to choose $n$ out of $2n$.

Consider the coefficient of $x^n$ in $(1+x)^{2n}$. We have $$(1+x)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}x^k=(1+x)^n(1+x)^n= \Big(\sum_{k=0}^{n}\binom{n}{k}x^k\Big)\Big(\sum_{k=0}^{n}\binom{n}{k}x^{n-k}\Big).$$ The coefficient of $x^n$ is equal to $\binom{2n}{n}$ in the left hand side.

The coefficient of $x^n$ is equal to $\sum_{k=0}^n\binom{n}{k}^{\!2}$ in the right hand side.

It seems the following.

$$\sum_{k=0}^{n}\begin{pmatrix}n\\k\end{pmatrix}=(1+1)^n=2^n.$$ $$\sum_{k=0}^{n}\begin{pmatrix}n\\k\end{pmatrix}^2=\begin{pmatrix}2n\\n\end{pmatrix}$$

To prove the last inequality it suffice to calcuate the coefficient by $x^n$ at both sides of the equality

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