The Archive

To see problems and solutions in the fall series, which runs from October 13 through December 15 visit The Fall 2025 Featured Problem Series

Problem

The following comes from Paul Hoffman’s book, "The Man Who Loved Only Numbers" ( Paperback edition, 1999, p.95).

There is a much quoted story about David Hilbert, who one day noticed that a certain student had stopped attending class. When told that the student had decided to drop mathematics to become a poet, Hilbert replied, "Good– he did not have enough imagination to become a mathematician."

-Robert Osserman

Penn State Math 310, a sophomore-level course in combinatorics, is our source for this week’s problem. We love combinatorial proofs because they require imagination. This week’s problem is no exception.

Use a combinatorial argument (a proof that demonstrates that both sides of the equation count the same set of objects) to prove that for ,

Solution

Suppose that is a finite set with elements. Denote the power set of , i.e. the collection of all subsets of , by . It is argued that both sides of count the cardinality of defined by where is the cardinality of . Two procedures for constructing are considered.

Procedure 1: First, select the singleton by selecting a single element of . There are ways to do this. Next, form the subset , by selecting a subset of arbitrary size from the set . Since and , . Therefore there are subsets of . The multiplication rule gives . This is the right hand side of .

Procedure 2: The construction is broken down into cases based on the cardinality of . The general case is to form a pair with , and , .

The formation of this pair is carried out in two steps. The first step is to select with . There are ways this can be done. Next, and are constructed from by selecting a single element of to form , and then setting . Observe that , , gives Thus has the desired cardinality. There are ways to form and only one way to form . Hence, by the product rule, the total number of ways to construct a singleton and a subset of elements which is disjoint from the singleton is . The sum rule gives , which is the left hand side of .

It follows that