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


5 Answers 5


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.

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


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

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

  • 3
    $\begingroup$ This is a combinatorial proof, which is contrary to what OP wanted. $\endgroup$
    – Batman
    May 13, 2014 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.