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?
On
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.
On
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$.
On
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}.$$
$$ {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 $$