7
$\begingroup$

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

$\endgroup$
14
$\begingroup$

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.

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

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

$\endgroup$
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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?$$ $\endgroup$ – chs21259 Jul 8 '14 at 2:12
  • $\begingroup$ @chs21259 That follows from the binomial theorem. $\endgroup$ – Dan Z Jul 8 '14 at 2:39
  • $\begingroup$ @DanZollers oh wow, duh, thanks Dan $\endgroup$ – chs21259 Jul 8 '14 at 2:40
1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ This is a combinatorial proof, which is contrary to what OP wanted. $\endgroup$ – Batman May 13 '14 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.