Htykuut

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)^ncdot(1+x)^n$. By the binomial theorem we have $displaystyle(1+x)^n=sum_{k=0}^n{nchoose k} x^k$, so multiplying out we compute the right hand side as $displaystyle(1+x)^ncdot(1+x)^n = sum_{k=0}^{2n}left(sum_{j=0}^k{nchoose j}{nchoose k-j}x^kright)$. But the LHS is just $displaystyle(1+x)^{2n} = sum_{k=0}^{2n}{2nchoose k}x^k$; equating coefficients of $x^n$ we get $displaystyle{2nchoose n}=sum_{j=0}^n {nchoose j}{nchoose n-j}$. Finally, using the identity ${nchoose j}={nchoose n-j}$ gives the desired result.

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}^kbinom{n}{j}binom{m}{k-j}.$$

$newcommand{+}{^{dagger}}
newcommand{angles}[1]{leftlangle, #1 ,rightrangle}
newcommand{braces}[1]{leftlbrace, #1 ,rightrbrace}
newcommand{bracks}[1]{leftlbrack, #1 ,rightrbrack}
newcommand{ceil}[1]{,leftlceil, #1 ,rightrceil,}
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]{,leftlfloor #1 rightrfloor,}
newcommand{half}{{1 over 2}}
newcommand{ic}{{rm i}}
newcommand{iff}{Longleftrightarrow}
newcommand{imp}{Longrightarrow}
newcommand{isdiv}{,left.rightvert,}
newcommand{ket}[1]{leftvert #1rightrangle}
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]{leftvert, #1 ,rightvert}
newcommand{wt}[1]{widetilde{#1}}$
${ttcolor{#f00}{mbox{This method is a "direct calculation" which is very}}}$
${ttcolor{#f00}{mbox{ convenient when we don't know the answer and, in addition,}}}$
${ttcolor{#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 2piic}
$$

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 2piic}
\[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 2piic}
\[3mm]&=oint_{verts{z} = 1}{pars{1 + z}^{n} over z}
pars{1 + {1 over z}}^{n},{dd z over 2piic}
=oint_{verts{z} = 1}{pars{1 + z}^{2n} over z^{n + 1}},{dd z over 2piic}
\[5mm] = &
bbox[10px,border:1px groove navy]{2n choose n}
end{align}

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