The Art and Craft of Problem Solving

198 CHAPTER 6 COMBINATORICS

This method certainly generalizes to sets with n elements, so we have proven that

the number of subsets of a set with n elements is 2 n. Combining this with our previous

partitioning argument, we have the combinatorial identity

Isub(S) (^1) = (�) + G) + G) + ... + G) =^2 n.
Let us look at a few more examples that explore the interplay among encoding,
partitioning, and the use of combinatorial argument.
Example 6.2.1 Prove that for all positive integers n,
(2)
Solution: One approach, of course, is to ignore the combinatorial aspect of the
identity and attack it algebraically. We must compute }:r r (�). Since we understand
the simpler sum }:r C), it might be profitable to try to remove the difficult r factor
from each term of (2):

r= 1 f r(�) = r=1 f r!(��r)!

n rn!

=

r� 1 r(r- l)!(n -r)!

n n!

=

r� 1 (r-l)!(n-r)!

n n(n-l)!

=

r� 1 (r - l)!(n -r)!

= n2

n-l.

The algebraic manipulations used here may seem to come out of thin air, but they

are motivated by strategy. We start with a complicated sum, and deliberately strive to

make its terms look like a simpler sum that you already know. Since the right-hand

side of (2) is n2n-l, it is plausible to see if the left-hand side can merely be turned

into n times a simpler sum that equals 2 n-l. This is just another example of using the

wishful thinking and penultimate step strategies, perhaps the most useful combination

in problem solving. And do note the careful use of factoring to extract, for example,

(n -I)! from n!, as well as the use of the interesting identity

G) = � G = !).

While this algebraic proof is elegant and instructive, in a sense it is an empty

argument, for the terms in (2) obviously have combinatorical meaning that we have

ignored. Let us now prove it with combinatorial reasoning.