3
$\begingroup$

I came across the following combinatorial identity:

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

Here's the kind of proof which caught my interest:

$\sum_k {n \choose k}^2 = \sum_k {n \choose k}{n \choose n - k}$, and this represents the number of ways we might choose a committee of $n$ people out of a group of $2n$ people. On the other hand, ${2n \choose n}$ represents the same thing. So the result follows.

Now, I'm looking for some nice combinatorial identities which are, in spirit, similar to such an identity.

Thank you.

$\endgroup$
4
  • 1
    $\begingroup$ There's quite a lot of nice things here: en.wikipedia.org/wiki/Binomial_coefficient including a proof of your identity $\endgroup$
    – GiantTortoise1729
    Commented Jul 5, 2015 at 23:08
  • 1
    $\begingroup$ @JackD'Aurizio: did you bother reading the question? $\endgroup$
    – user230734
    Commented Jul 6, 2015 at 1:06
  • $\begingroup$ The Google search "combinatorial argument" OR "combinatorial proof" site:math.stackexchange.com will turn up many examples. $\endgroup$
    – Brian M. Scott
    Commented Jul 6, 2015 at 3:48
  • $\begingroup$ As an aside, letting $n=\dfrac12$ in the identity you quoted, we get a formula for $\pi$. $\endgroup$
    – Lucian
    Commented Jul 6, 2015 at 7:16

1 Answer 1

Reset to default
3
$\begingroup$

There is a book called "Proofs that Really Count: The Art of Combinatorial Proof" by Arthur T. Benjamin and Jennifer J. Quinn, which might be of interest to you.

$\endgroup$
1
  • 1
    $\begingroup$ Also the downloadable book "A-B" on methods for automatically discovering and proving combinatorial identities by Wilf, et al. $\endgroup$
    – hardmath
    Commented Jul 6, 2015 at 2:38