# Non-inductive, not combinatorial proof of $\sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$

I've seen the identity $\displaystyle \sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$ used here recently.

I checked for proofs here http://www.proofwiki.org/wiki/Sum_of_Squares_of_Binomial_Coefficients

I couldn't have figured out the combinatorial proof by myself, and the inductive proof assumes you already know the answer...

So my question is : do you know how to prove directly through computation that $\displaystyle \sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$ ?

Consider the identity $(1+x)^{2n}=(1+x)^n\cdot(1+x)^n$. By the binomial theorem we have $\displaystyle(1+x)^n=\sum_{k=0}^n{n\choose k} x^k$, so multiplying out we compute the right hand side as $\displaystyle(1+x)^n\cdot(1+x)^n = \sum_{k=0}^{2n}\left(\sum_{j=0}^k{n\choose j}{n\choose k-j}x^k\right)$. But the LHS is just $\displaystyle(1+x)^{2n} = \sum_{k=0}^{2n}{2n\choose k}x^k$; equating coefficients of $x^n$ we get $\displaystyle{2n\choose n}=\sum_{j=0}^n {n\choose j}{n\choose n-j}$. Finally, using the identity ${n\choose j}={n\choose n-j}$ gives the desired result.

• (and use the identity that $n\choose i$=$n\choose n-i$) May 13, 2014 at 15:16
• (Using the binomial formula, of course.) May 13, 2014 at 15:16
• @StevenStadnicki, With the current version, we don't need that Identity May 13, 2014 at 15:26
• @labbhattacharjee I think you do need it after Cauchy product. May 13, 2014 at 15:29
• I fail to see how this is a proof. May 13, 2014 at 15:55

lab bhattacharjee has given the proof, but it is worth pointing out that this formula is simply an application of the Vandermonde convolution, which says that

$$\sum_{j=0}^k \binom{n}{j}\binom{m}{k-j} = \binom{n+m}{k}.$$

Setting $n=m=k$ and noting that $\binom{n}{n-j}=\binom{n}{j}$ gives the result.

EDIT: By the way, for a slightly non-standard (but purely technical, as you require) proof of the Vandermonde convolution, let $X_1,\cdots,X_{n+m}$ be independent Bernoulli distributed RV's with parameter $p=1/2$. Then, $S_{n+m}=\sum_{j=0}^{n+m}X_j$ has binomial distribution $P[S_{n+m}=k]=\binom{n+m}{k}(\frac{1}{2})^{n+m}$. Applying the ordinary discrete convolution formula for probability distributions yields

$$(1/2)^{n+m}\binom{n+m}{k}=P[S_{n+m}=k]=\sum_{j=0}^k P[S_n=j]P[S_m=k-j]=(1/2)^{n+m}\sum_{j=0}^k\binom{n}{j}\binom{m}{k-j}.$$


It's based in the identity:

$${m \choose s} =\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{m} \over z^{s + 1}}\,{\dd z \over 2\pi\ic}$$

\begin{align} &\bbox[10px,#ffd]{\sum_{k = 0}^{n}{n \choose k}^{2}} = \sum_{k = 0}^{n}{n \choose k} \oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{n} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{n} \over z} \sum_{k = 0}^{n}{n \choose k}\pars{1 \over z}^{k} \,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{n} \over z} \pars{1 + {1 \over z}}^{n}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{2n} \over z^{n + 1}}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \bbox[10px,border:1px groove navy]{2n \choose n} \end{align}

• very cool, any tip on how to show $$\sum_{k=0}^{n}\binom{n}{k}\left(\frac{1}{z}\right)^k = \left(1+\frac{1}{z}\right)^n?$$ Jul 8, 2014 at 2:12
• @chs21259 That follows from the binomial theorem. Jul 8, 2014 at 2:39
• @DanZollers oh wow, duh, thanks Dan Jul 8, 2014 at 2:40

You're after a sum of a hypergeometric term. There are general techniques for finding closed forms or proving that they don't exist. See e.g. the book A = B, or MathWorld's description of Sister Celine's method, Gosper's algorithm, and Zeilberger's algorithm.

Note that we can divide the $2n$ objects in $2$ groups including $n$ elements each.

Then to choose $n$ elements out of $2n$ we can choose $0$ objects in the first group and $n$ in the second, or $1$ in the first and $n-1$ in the second and so on, i.e $$\binom{2n}{n} = \sum_{i = 0}^{2n}\binom{n}{i}\binom{n}{n-i} =\sum_{i = 0}^{2n}{\binom{n}{i}}^2$$

• This is a combinatorial proof, which is contrary to what OP wanted. May 13, 2014 at 17:43