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.

For the record, what we found is that n(1 + x)^n-1 is the generating function for the sequence {kC(n, k)}. This observation leads directly to the evaluation of the average in the binomial distribution.

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

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

Pascal's Triangle and the Binomial Coefficients

• Arithmetic in Disguise
• Construction of Pascal's Triangle
• Dot Patterns, Pascal Triangle and Lucas Theorem
• Integer Iterations on a Circle
• Leibniz and Pascal Triangles
• Lucas' Theorem
• Patterns in Pascal's Triangle
• Random Walks
  • The Ballot Lemma
  • The Reflection Lemma
• Sierpinski Gasket and Tower of Hanoi
• Treatise on Arithmetical Triangle
• Ways To Count

Copyright © 1996-2010 Alexander Bogomolny