60
$\begingroup$

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

  • 16
    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.2012-05-23
  • 6
    This is secretly subsumed by [this question](http://math.stackexchange.com/questions/113267/proof-of-displaystyle-sum-0-le-k-le-a-a-choose-k-b-choose-k-ab)2012-05-23
  • 2
    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.2012-05-23
  • 7
    I think your combinatorial proof is really nice, and you should not be unhappy with it.2012-05-23
  • 2
    Incidentally, this is a special case of http://math.stackexchange.com/questions/337923/summations-with-binomial-coefficients-sum-k-0n-binomrk-binommn-k.2013-11-16
  • 0
    [It appears](http://math.stackexchange.com/questions/18690/algebraic-proof-that-sum-limits-i-0n-binomni-2n) in the M.SE "frequent questions" sections.2014-07-17
  • 0
    @FelixMarin You linked to a question asking about $\sum\binom{n}{i}=2^n$. Did you mean to link to something else?2015-04-09
  • 0
    If you want to see a linear-algebraic proof (a la construction of fibonacci numbers by a $2\times 2$ matrix, I just posted the outline at http://math.stackexchange.com/a/1954319/161506).2016-10-05

6 Answers 6