How do I show that $\sum_{k = 0}^n \binom nk^2 = \binom {2n}n$? $$\sum_{k = 0}^n \binom nk^2 = \binom {2n}n$$
I know how to "prove" it by interpretation (using the definition of binomial coefficients), but how do I actually prove it?
 A: I am not sure if you consider this proof analytic: Write $D = d/dx$. From the Leibniz rule, we have
\begin{align*}
\frac{(2n)!}{n!}
= D^n x^{2n} |_{x=1}
&= D^n (x^n \cdot x^n) |_{x=1} \\
&= \sum_{k=0}^{n} \binom{n}{k} (D^k x^n)(D^{n-k} x^n) |_{x=1} \\
&= \sum_{k=0}^{n} \binom{n}{k} \frac{n!}{(n-k)!} \frac{n!}{k!}.
\end{align*}
Then the identity follows by dividing both sides by $n!$ and simplifying it.
A: A combinatorial proof
How many ways can we pick $n$ objects from a selection of $2n$?
Consider the $2n$ objects to be $$(1,1), (1,2), (2,1), (2,2), \dots, (n, 1), (n, 2)$$
Then the number of ways we can pick out $n$ of these is equal to the number of ways we can pick out $n$ conditioning on how many we select with second coordinate $1$.
That is, $$\sum_{k=0}^n \text{ways to select $k$ with $1$-coordinate} \times \text{ways to select $n-k$ with $2$-coordinate}$$
The summand is clearly $$\binom{n}{k} \times \binom{n}{n-k}$$
But that is $$\binom{n}{k} \times \binom{n}{k} = \binom{n}{k}^2$$
A: A Complex-Analytic (~Algebraic) Proof
For $z\in\mathbb{C}\setminus\{0\}$, $\sum\limits_{k=0}^n\,\binom{n}{k}\,\frac{(1+z)^n}{z^{k+1}}=\frac{(1+z)^n}{z}\,\sum\limits_{k=0}^n\,\binom{n}{k}\,\frac{1}{z^k}=\frac{(1+z)^n}{z}\,\left(1+\frac{1}{z}\right)^n=\frac{(1+z)^{2n}}{z^{n+1}}$.  Thus, if $\gamma$ is a curve that counterclockwise wounds around the origin once, then
$$\begin{align}
\sum_{k=0}^n\,\binom{n}{k}^2=\sum_{k=0}^n\,\binom{n}{k}\,\binom{n}{k}&=\sum\limits_{k=0}^n\,\binom{n}{k}\,\left(\frac{1}{2\pi\mathrm{i}}\,\oint_{\gamma}\,\frac{(1+z)^n}{z^{k+1}}\,\text{d}z\right)
\\&=\frac{1}{2\pi\mathrm{i}}\,\oint_{\gamma}\,\sum\limits_{k=0}^n\,\binom{n}{k}\,\frac{(1+z)^n}{z^{k+1}}\text{d}z
\\&=\frac{1}{2\pi\mathrm{i}}\,\oint_{\gamma}\,\frac{(1+z)^{2n}}{z^{n+1}}\text{d}z=\binom{2n}{n}\,.
\end{align}$$
A: To prove binomial identities it is often convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$.  So, we can write e.g.
\begin{align*}
\binom{n}{k} = [x^k](1+x)^n\tag{1}
\end{align*}
Note,  this is essentially the same approach as that of @Batominovski but with a somewhat more algebraic look and feel.

We obtain
  \begin{align*}
\sum_{k=0}^{n}\binom{n}{k}^2&=\sum_{k=0}^{n}[x^k](1+x)^n[t^k](1+t)^n\tag{2}\\
&=[x^0](1+x)^n\sum_{k=0}^{n}x^{-k}[t^k](1+t)^n\tag{3}\\
&=[x^0](1+x)^n\left(1+\frac{1}{x}\right)^n\tag{4}\\
&=[x^n](1+x)^{2n}\tag{5}\\
&=\binom{2n}{n}
\end{align*}

Comment:


*

*In (2) we use the coefficient of operator twice according to (1)

*In (3) we use the linearity of the coefficient of operator and the rule $$[x^n]x^{-k}P(x)=[x^{n+k}]P(x)$$

*In (4) we use the substitution rule and apply $x\rightarrow \frac{1}{x}$
\begin{align*}
P(x)&=\sum_{k=0}^na_kx^k=\sum_{k=0}^nx^k[t^k]P(t)\\
P\left(\frac{1}{x}\right)&=\sum_{k=0}^na_kx^{-k}=\sum_{k=0}^nx^{-k}[t^k]P(t)
\end{align*}

*In (5) we use $\left(1+\frac{1}{x}\right)^n=x^{-n}(1+x)^n$ and $[x^0]x^{-n}=[x^n]$
