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

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ ${\tt\color{#f00}{\mbox{This method is a "direct calculation" which is very}}}$ ${\tt\color{#f00}{\mbox{ convenient when we don't know the answer and, in addition,}}}$ ${\tt\color{#f00}{\mbox{ we don't have to guess combinations of Newton binomials.}}}$

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}