Ways To Count

The purpose of this page is to present several proofs of an identity that involves binomial coefficients:

Four such proofs have been collected in a 1999 issue of Crux Mathematicorum by Jimmi Chui, then a secondary school student. I found two more elsewhere and present all six below.

Pure Algebra

Let S denotes the sum in (1). Using the basic property of the binomial coefficients C(n, k) = C(n, n - k) we have

Adding the first and the last sums gives

which immediately applies (1).

We shall prove (1) by mathematical induction. For n = 1, there is nothing to prove. Assume (1) holds for some n = k:

If the left side (2) is denoted S(k), we have using the addition formula

Consider the generating function for the binomial coefficients:

The derivative of which is

So that f '(1) = S(n). On the other hand, by the binomial theorem,

with the derivative

from which f '(1) = n2^n-1.

We may also start by selecting the chairperson first and then complementing the committee by regular members out of the remaining n-1 fellows. There are n choices for the chairperson and 2^n-1 possibilities for other members, which gives the right hand side in (1).

Combinatorial Proof 2

The expression S(n)/2ⁿ [Benjamin & Quinn, p. 66] also has a combinatorial interpretation. It answers the question, "What is the average size of a subset of {1, 2, ..., n}?" Indeed, there are exactly C(n, k) subsets with k terms whereas 2ⁿ is the total number of the subsets.

On the other hand, pair each subset with its complement. The two together have n terms and the average of n/2. So that

which is equivalent to (1).

Formula for Binomial Coefficients

Recollect that [Zeitz, p. 215]

Then

where the sum is taken from k = 1 to k = n. Thus

Applying the binomial theorem.

References

1. A. T. Benjamin, J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, MAA, 2003
2. P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999

Copyright © 1996-2008 Alexander Bogomolny