Another Binomial Identity with Proofs

The purpose of this page is to present two proofs of an identity that involves binomial coefficients. I'll be using a shorter than usual notation ${n \choose m}$ for the binomial coefficient $C^{n}_{m}$.

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

Combinatorial Proof

Recollect that ${n \choose k}={n \choose n-k}$ and rewrite the required identity as

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

In this form it admits a simple interpretation. It is required to select an $n$-members committee out of a group of $n$ men and $n$ women. The number of possibilities is ${2n \choose n}$, the right hand side of the identity.

On the other hand, if the number of men in a group of $n$ grownups is $k$ then the number of women is $n-k$, and all possible variants are expressed by the left hand side of the identity.

Proof with Generating Functions

$(1+x)^n$ is the generating function for the binomial coefficients ${n \choose k}, 0\le k\le n$. Obviously, $(1+x)^{n}(1+x)^{n}=(1+x)^{2n}$. On the right, the coefficient by $x^n$ is ${2n \choose n}.$ On the left, it is $\sum_{k=0}^{n}{n \choose k}{n \choose n-k}$.

In fact, with a little change of the language, we can prove a more general identity:

$\displaystyle\sum_{k\ge 0}{n \choose k}{m \choose k}={n+m \choose n}.$

(The assumption here is that, for $a\lt b,\space {a \choose b}=0$.)

For a combinatorial argument, the number of men $n$ is not necessarily equal to the number of women $m$. With generating functions, we use $(1+x)^{n}(1+x)^{m}=(1+x)^{n+m}$.

References

  1. A. T. Benjamin, J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, MAA, 2003
  2. R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.

Combinatorial Proofs

  1. Combinatorial Proofs.
  2. Lucas' Theorem.
  3. Ways To Count.
  4. Geometric Proof of Wilson's Theorem.
  5. Partitioning a Circle
  6. A Minesweeper Theorem
  7. Another Binomial Identity with Proofs
  8. Counting Fat Sets
  9. Counting Permutations with Fixed Points
  10. Pythagorean Triples via Fibonacci Numbers

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

70571053