I was hoping to find a more "mathematical" proof, instead of proving logically $\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$.

I already know the logical Proof:

$${n \choose k}^2 = {n \choose k}{ n \choose n-k}$$

Hence summation can be expressed as:

$$\binom{n}{0}\binom{n}{n} + \binom{n}{1}\binom{n}{n-1} + \cdots + \binom{n}{n}\binom{n}{0}$$

One can think of it as choosing $n$ people from a group of $2n$ (imagine dividing a group of $2n$ into $2$ groups of $n$ people each. I can get $k$ people from group $1$ and another $n-k$ people from group $2$. We do this from $k = 0$ to $n$.

  • 22
    $\begingroup$ Just FYI, what you call a "logical proof" is known as a "combinatorial proof", and such a proof is perfectly valid and often very insightful. What I suspect you mean by "mathematical proof" is one dealing with the numerical structure of sums and combinations, which would be better called an "analytical proof". Both styles of proof are equally mathematical. $\endgroup$ May 23 '12 at 4:57
  • 7
    $\begingroup$ This is secretly subsumed by this question $\endgroup$
    – davidlowryduda
    May 23 '12 at 5:00
  • 2
    $\begingroup$ You could obtain the same combinatorial proof by noting that $\binom{2n}{n}$ counts the number of paths from $(0,0)$ to $(n,n)$ on an $n\times n$ grid. $\endgroup$ May 23 '12 at 6:03
  • 8
    $\begingroup$ I think your combinatorial proof is really nice, and you should not be unhappy with it. $\endgroup$
    – MJD
    May 23 '12 at 13:54
  • 3
    $\begingroup$ Incidentally, this is a special case of math.stackexchange.com/questions/337923/…. $\endgroup$
    – NNOX Apps
    Nov 16 '13 at 10:26

The combinatorial explanation is straightforward. There's also a roundabout approach through what are called "generating functions." The binomial theorem tells us that


The $x^n$ coefficient of the above occurs with $c=n$, wherein the coefficient is


However, the $x^n$ coefficient of $(1+x)^n(x+1)^n=(1+x)^{2n}$, again by the binomial theorem, is

$$\binom{2n}{n}. $$

Equating the two gives the result.

  • 1
    $\begingroup$ +1. @Lance C Do you see that this is the same as your "logical" proof? Choosing $n$ people from $2n$ is what you are doing when you look at the coefficient of $x^n$ in the expansion. $\endgroup$
    – user17762
    May 23 '12 at 5:12
  • $\begingroup$ Can you explain me in more detail... why $\sum_{a=0}^n\binom{n}{a}x^a $ * $\sum_{b=0}^n\binom{n}{b}x^{n-b}$ is equal to $\sum_{c=0}^{2n} \sum_{a+n-b=c}\binom{n}{a}\binom{n}{b} x^c$ please $\endgroup$
    – Salvattore
    Jul 25 '14 at 4:59
  • 1
    $\begingroup$ @Salvattore $\sum_{a,b}\binom{n}{a}\binom{n}{b}x^{a+n-b}$, then collect all the coefficients of $x^c$ for fixed $c$ into $\sum_{a+n-b=c}\binom{n}{a}\binom{n}{b}$ to get $\sum_c\left[\sum_{a+n-b=c}\binom{n}{a}\binom{n}{b}\right]x^c$. If you want to work with generating functions, or even just plain polynomials, you need to be able to collect like terms, it is virtually a requirement. $\endgroup$
    – anon
    Jul 29 '14 at 17:23

Since $\dbinom n k= \dbinom n {n-k}$, the identity $$ \sum_{k=0}^n \binom n k ^2 = \binom {2n} n $$ is the same as $$ \sum_{k=0}^n \binom n k \binom n {n-k} = \binom {2n} n. $$ So say a committee consists of $n$ Democrats and $n$ Republicans, and one will choose a subcommittee of $n$ members. One may choose $k$ Democrats and $n-k$ Republicans in $\dbinom n k \cdot \dbinom n {n-k}$ ways. The number of Democrats is in the set $\{0,1,2,\ldots,n\}$, thus ranging from all Republicans to all Democrats. The sum then gives the total number of ways to choose $n$ out of $2n$.


$\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{\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{\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}$ \begin{align} \color{#66f}{\large\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} \\[5mm]&=\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{n} \over z} \pars{1 + {1 \over z}}^{n}\,{\dd z \over 2\pi\ic} \\[5mm] & = \oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{2n} \over z^{n + 1}}\,{\dd z \over 2\pi\ic} \\[5mm] & =\color{#66f}{\large{2n \choose n}} \end{align}

  • $\begingroup$ Can we change integral and summation? What is the reason behind that ? $\endgroup$ Jan 4 '17 at 4:23
  • $\begingroup$ @SiddhantTrivedi In this case, it's just a $finite$ sum. $\endgroup$ Jan 5 '17 at 22:27
  • $\begingroup$ In the general case of Vandermonde's identity, we can pull the same trick, by adding terms with no singularity (so their contour integral is zero) when we get to line 2 and 3 of your proof. $\endgroup$ Dec 12 '19 at 17:02
  • $\begingroup$ can you please provide some more details, so that from there I can learn this in details. $\endgroup$ Dec 22 '20 at 5:39

Consider the graph underlying Pascal's triangle: Pascal's triangle

In this graph, the number at each node is a binomial coefficient and can also be thought of as the number of downward paths from the apex to that node.

The left side of the identity is the number of paths that start at the apex, go down to the $n$th row and return to the apex (let's call them round trips to $n$). By reflecting the return path about the $n$th row, we get a bijective correspondence between return trips to $n$ and paths from the apex to the central node of the $2n$th row. This is nothing but the central binomial coefficient $\binom{2n}n$.


Okey this one is easy(if you seen this one once) We have to show: $${n \choose 0}^2+{n \choose 1}^2+\cdots+{n \choose n}^2={2n \choose n} $$ Define a set A, $$A=\{a_1,\ldots,a_n,a_{n+1},\ldots,a_{2n}\}$$ consisting of $2n$ - Elements. Now we declare $V$, is a set of $n$-sets of $A$. Obviously the cardinality of $V,$ $$|V|={2n \choose n}.$$ Since one can choose $n$ Elements from $2n$ Elements in $${2n \choose n}$$ ways.

Okey now we have the right side. The for the left side you have give a disjunctive partition of the $V$ set. This should be done in the following way: $V_i$ has exactly $i$-Elements from ${a_1,\ldots,a_n}$, then the cardinality $|V_i|={n \choose i}{n \choose n-i}={n \choose i}{n \choose i}={n \choose i}^2$. Then with the Rule of Sum we have the left side. And we are done. The Tricky Part ist to create the Partition to use the rule of sum.


Considerando que el producto de polinomios se puede expresar de la siguiente forma $$\sum_{l=0}^{2n}(\sum_{k=0}^{l}(b_{k})(a_{l-k}))x^l=(a_0+a_1x+...+a_nx^n)(b_0+b_1x+...+b_nx^n)$$

En particular $$\sum_{l=0}^{2n}(\sum_{k=0}^{l}\binom{n}{k}\binom{n}{l-k})x^l=(1+x)^{n}(1+x)^{n}=(1+x)^{2n}=\sum_{l=0}^{2n} \binom{2n}{l}x^l$$

$$\sum_{l=0}^{2n}(\sum_{k=0}^{l} \binom{n}{k}\binom{n}{l-k})x^l=\sum_{l=0}^{2n} \binom{2n}{l}x^l$$

Para cualquier l se tiene que

$$(\sum_{k=0}^{l} \binom{n}{k}\binom{n}{l-k})x^l=\binom{2n}{l}x^l$$

En particular para l = n

$$\sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k}=\binom{2n}{n}$$

$$\sum_{k=0}^{n} \binom{n}{k}\binom{n}{k}=\binom{2n}{n}$$

$$\sum_{k=0}^{n} \binom{n}{k}^2=\binom{2n}{n}$$


  • 3
    $\begingroup$ Sir, is it possible to convert your statements into English? $\endgroup$ Apr 3 at 8:53

Imagine that we are distributing $n$ indistinguishable candies to $k$ distinguishable children. By a direct application of Balls and Urns, there are $${n+k-1\choose k-1}$$ ways to do this. Alternatively, we can first give $0\le i\le n$ candies to the oldest child so that we are essentially giving $n-i$ candies to $k-1$ kids and again, with Balls and Urns, $${n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}$$, which simplifies to the desired result.


By double count Imagine you want to make teams with n people and you have n boys and n girl you can make this by choosing n people between 2n people that is $2n \choose n$ but another way to count this is by choosing how many boys you want in each step for example if you want to have 3 boys, then there are ${n \choose 3}*{n \choose n-3}={n \choose 3}^2$ ways to do this, think it for a little you can choose from 0 to n boys in your teamn then the number of teams with n people is $\sum_{k = 0}^n {n \choose k}^2$


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.