Another Binomial Identity with Proofs (original) (raw)

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 nchoosem{n \choose m}nchoosem for the binomial coefficient CnmC^{n}_{m}Cnm. displaystylesumk=0nnchoosek2=2nchoosen.\displaystyle\sum_{k=0}^{n}{n \choose k}^{2}={2n \choose n}.displaystylesumk=0nnchoosek2=2nchoosen.

Combinatorial Proof

Recollect that nchoosek=nchoosen−k{n \choose k}={n \choose n-k}nchoosek=nchoosen−k and rewrite the required identity as displaystylesumk=0nnchooseknchoosen−k=2nchoosen.\displaystyle\sum_{k=0}^{n}{n \choose k}{n \choose n-k}={2n \choose n}.displaystylesumk=0nnchooseknchoosen−k=2nchoosen.

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

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

Proof with Generating Functions

(1+x)n(1+x)^n(1+x)n is the generating function for the binomial coefficients nchoosek,0leklen{n \choose k}, 0\le k\le nnchoosek,0leklen. Obviously, (1+x)n(1+x)n=(1+x)2n(1+x)^{n}(1+x)^{n}=(1+x)^{2n}(1+x)n(1+x)n=(1+x)2n. On the right, the coefficient by xnx^nxn is 2nchoosen.{2n \choose n}.2nchoosen. On the left, it is sumk=0nnchooseknchoosen−k\sum_{k=0}^{n}{n \choose k}{n \choose n-k}sumk=0nnchooseknchoosen−k.

In fact, with a little change of the language, we can prove a more general identity: displaystylesumkge0nchoosekmchoosek=n+mchoosen.\displaystyle\sum_{k\ge 0}{n \choose k}{m \choose k}={n+m \choose n}.displaystylesumkge0nchoosekmchoosek=n+mchoosen.

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

For a combinatorial argument, the number of men nnn is not necessarily equal to the number of women mmm. With generating functions, we use (1+x)n(1+x)m=(1+x)n+m(1+x)^{n}(1+x)^{m}=(1+x)^{n+m}(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