A Committee and Its Chair
The puzzle
From five people, form a committee of any non-empty size and appoint one of its members as chair.
In how many ways? Count it two different ways and you have proved an identity.
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
Way one: pick the committee first, then the chair from within it.
Hint 2
Way two: pick the chair first, then decide independently for each remaining person whether they join.
Show the answer Hide the answer
80. Counting it both ways proves that the sum of k × C(n,k) equals n × 2^(n−1).
How to get there
Chair first: 5 ways to choose the chair, then each of the other 4 people is independently in or out - 2^4 = 16 ways. Total 5 × 16 = 80.
Committee first: a committee of size k can be chosen in C(5,k) ways and has k choices of chair. Summing k × C(5,k) over k = 1 to 5 gives 1×5 + 2×10 + 3×10 + 4×5 + 5×1 = 5 + 20 + 30 + 20 + 5 = 80. The same.
Since both count the same thing, they are equal for every n: the sum of k C(n,k) is n 2^(n−1). The second route is a five-term sum; the first is one multiplication - which is the point of looking for another way to count.
The technique worth keeping
Counting one set two ways proves an identity, and usually one of the two ways is far easier. Choosing the distinguished element FIRST turns a sum over sizes into a single product.