How do I show that $\sum_{k = 0}^n \binom nk^2 = \binom {2n}n$? [duplicate]

$$\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?

marked as duplicate by Jean-Claude Arbaut, Claude Leibovici, Ian Miller, choco_addicted, user91500Apr 6 '16 at 6:37

• One common algebraic proof uses the fact that $\binom{n}{k}=\binom{n}{n-k}$ to reduce the problem to showing $\sum \binom{n}{k}\binom{n}{n-k}=\binom{2n}{n}$ and then observe that $\binom{2n}{n}$, the $n$-th coefficient of $(1+x)^{2n}=((1+x)^n)^2=(\sum \binom{n}{k}x^{k})^2$ is $\sum \binom{n}{k}\binom{n}{n-k}$. – cjackal Apr 4 '16 at 7:58
• @cjackal Thank you. Actually my interpretation is based on the fact that $\sum_{k=0}^n\binom nk \binom n{n-k}=\binom {2n}n$. – Colescu Apr 4 '16 at 8:02
• Well then what do you mean in saying "analytically"? I think generating functionology is usually considered as analytic... – cjackal Apr 4 '16 at 8:04
• You can have a look at math.stackexchange.com/questions/670672/… and math.stackexchange.com/questions/404715/… (and other posts linked there). You can find several proofs there (induction, binomial theorem). – Martin Sleziak Apr 4 '16 at 10:09
• I see some discussion about it already, but what do you mean exactly with algebraically? – Eric S. Apr 4 '16 at 14:37

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 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 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$$

• This is actually the same as my interpretation. But, seriously, can it really be regarded as a proof? Since this method is developed using mainly words, it doesn't seem as reliable or rigorous. – Colescu Apr 4 '16 at 14:50
• @YuxiaoXie If you preferred, I could express it as the equality of the cardinalities of certain sets by providing bijections between them. I won't do that because it's tedious. – Patrick Stevens Apr 4 '16 at 14:51

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]$