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

Combinatorial Proofs
- Combinatorial Proofs.
- Lucas' Theorem.
- Ways To Count.
- Geometric Proof of Wilson's Theorem.
- Partitioning a Circle
- A Minesweeper Theorem
- Another Binomial Identity with Proofs
- Counting Fat Sets
- Counting Permutations with Fixed Points
- Pythagorean Triples via Fibonacci Numbers

|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
72533659