Ways To Count

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

(1)

C(n, 1) + 2·C(n, 2) + 3·C(n, 3) + ... + n·C(n, n) = n2^n-1.

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

S	= 0·C(n, 0) + 1·C(n, 1) + 2·C(n, 2) + ... + n·C(n, n)
	= 0·C(n, n) + 1·C(n, n-1) + 2·C(n, n-2) + ... + n·C(n, 0)
	= n·C(n, 0) + (n-1)·C(n, 1) + (n-2)·C(n, 2) + ... + 0·C(n, n).

Adding the first and the last sums gives

2S	= n·C(n, 0) + n·C(n, 1) + n·C(n, 2) + n·C(n, 3) + ... + n·C(n, n)
	= n·2n,

which immediately implies (1).

Mathematical Induction

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

(2)

C(k, 1) + 2·C(k, 2) + 3·C(k, 3) + ... + k·C(k, k) = k2^k-1.

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

S(k+1)	= C(k+1, 1) + 2·C(k+1, 2) + 3·C(k+1, 3) + ... + (k+1)·C(k+1, k+1)
	= 1·(C(k, 0) + C(k, 1)) + 2·(C(k, 1) + C(k, 2)) + ... + k·(C(k, k-1) + C(k, k)) + (k+1)C(k, k)
	= 1·C(k, 0) + 3·C(k, 1) + 5·C(k, 2) + ... + (2k+1)C(k, k)
	= (C(k, 0) + C(k, 1) + C(k, 2) + ... + C(k, k)) + 2·S(k)
	= 2k + 2·k·2k-1
	= (k + 1)·2k.

Generating functions

Consider the generating function for the binomial coefficients:

f(x) = C(n, 0) + C(n, 1)·x + C(n, 2)·x² + ... + C(n, n)·xⁿ

The derivative of which is

f '(x) = C(n, 1) + 2·C(n, 2)·x¹ + ... + n·C(n, n)·x^n-1.

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

f(x) = (1 + x)ⁿ,

with the derivative

f '(x) = n(1 + x)^n-1,

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.

Combinatorial Proof 1

Consider a set of n people. We shall answer the question, "In how many ways it is possible to select a (non-empty) committee and its chairperson from the set of n people?" We shall answer the question in two ways.

There are C(n, k) committees with k members (k ≥ 1) and, for each, there are k choices of a chairperson. Thus S(n) is the total number of such committees with a chair.

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

S(n)/2ⁿ = n/2,

which is equivalent to (1).

Formula for Binomial Coefficients

Recollect that [Zeitz, p. 215]

C(n, k) =

n! k!(n-k)!

Then

S(n)

= ∑

k·n! k!(n-k)!,

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

S(n)	= ∑	k·n! k!(n-k)!,
	= ∑	k·n! k·(k-1)!(n-k)!,
	= ∑	n! (k-1)!(n-k)!,
	= ∑	n·(n-1)! (k-1)!(n - k)!
	= n·∑	(n-1)! (k-1)!((n-1)-(k-1))!,

(The derivation might have been shortened by a reference to the well known formula kC(n, k) = nC(n-1, k-1), the absorbtion identity. The latter is verified directly from the definition of the binomial coefficients as was actually done above.)

Applying the binomial theorem.

S(n)	= n·∑C(n-1, k-1)
	= n·(C(n-1, 0) + C(n-1, 1) + ... + C(n-1, n-1))
	= n·2n-1,

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

Pascal's Triangle and the Binomial Coefficients

• Binomial Theorem
• 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
• Lucas' Theorem II
• 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
• Another Binomial Identity with Proofs
• Vandermonde's Convolution Formula
• Counting Fat Sets
• e in the Pascal Triangle
• Catalan Numbers in Pascal's Triangle
• Sums of Binomial Reciprocals in Pascal's Triangle
• Squares in Pascal's Triangle
• Cubes in Pascal's Triangle
• Pi in Pascal's Triangle

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

Copyright © 1996-2015 Alexander Bogomolny