September 2024
—————————
In the Math Corner of my September 2024 Diary I posted the following brainteaser.
Brainteaser: Here's a little oddity from the September issue of Math Horizon magazine. It's actually from what they call their Carousel: "an old problem that we like so much, we thought it deserved another go-round." It may be old to them, but it was new to me.
As an illustrative example, consider the set of the first four integers (i.e. whole numbers): {1, 2, 3, 4}. Now:
This doesn't just work for 4, it works for any positive integer. If you start with {1, 2, 3, …, n}, form all 2n−1 possible non-empty subsets, compute the product of the members for each subset, and add together the reciprocals of those products, you get n.
- Form all the non-empty subsets of those four numbers. Here they are: {1}, {2}, {2, 1}, {3}, {3, 1}, {3, 2}, {3, 2, 1}, {4}, {4, 1}, {4, 2}, {4, 2, 1}, {4, 3}, {4, 3, 1}, {4, 3, 2}, {4, 3, 2, 1}.
- There are 15 of these subsets. That makes sense: each of the four digits can be chosen or not chosen, giving 24 possibilities altogether. Ignore the single case where none are chosen, and there you are with 24−1 subsets.
- Plainly this can be generalized. If we were considering the first five numbers, {1, 2, 3, 4, 5} there would be 25−1 subsets, i.e. 31 … and so on.
- Now, for each subset compute the product of its members. For our fifteen subsets of {1, 2, 3, 4} that will give fifteen integers: 1, 2, 2, 3, 3, 6, 6, 4, 4, 8, 8, 12, 12, 24, 24.
- Add together the reciprocals of those fifteen product numbers: 1 + 1/2 + 1/2 + 1/3 + … + 1/24. Whaddya get? You get 4, the number we started with!
OK, so … prove it!
—————————
¶ Solution.
The statement we have to prove is that the sum of the reciprocals of the products of the members of each non-empty subset of {1, 2, 3, …, n} — call it S(n) — is equal to n for all integers n.
First, look hard at that list of subsets for n = 4.
- It's made up of two sublists, call them sublist A and sublist B. None of the subsets in sublist A contains a 4; all
of the subsets in sublist B do.
- Sublist A is just the list of subsets for n = 3. It's all possible non-empty subsets of
{1, 2, 3}.
- Sublist B is that same n = 3 list, but with a 4 inserted into each subset …
- … and with the extra subset {4}. That comes from inserting a 4 into the null subset {}. Since we're only
interested in non-empty subsets, {} doesn't make an appearance in sublist A.
- Plainly S(4) is just the sum of the reciprocals of the products of the members of each subset of sublist A plus the sum of
the reciprocals of the products of the members of each subset of sublist B.
- The first sum there is just S(3).
- Since each subset in sublist B except {4} is just some corresponding subset from the n = 3 list, but with a 4
inserted, the sum of the reciprocals of the products of the members of each subset of sublist B is S(3) / 4 …
- … plus an extra 1/4 from {4}.
- So S(4) = S(3) + S(3) / 4 + 1/4, which is 4.
With all that in mind, proof by induction looks promising for the general case.
Reminder: If we have to prove that some statement is true for all integers n, we can
- Prove it true for n = 1, then
- Prove that if it is true for some integer n, then it must also be true for n + 1.
That is proof by induction.
The statement we have to prove is that S(n), as defined — the sum of the reciprocals of the products of the members of each non-empty subset of {1, 2, 3, …, n} — is equal to n.
To prove that by induction we have to show that
- S(1) = 1, and
- If S(n) = n for some integer n, then S(n + 1) must be n + 1.
If n = 1, the only non-empty subset is {1}, the "product" (with only one number in the subset, we don't have to do any actual multiplying) is 1, and the reciprocal is 1, so the statement is true. Halfway there!
For some n greater than 1 we can follow the logic of n = 4: divide the list of subsets into sublist A (no subset contains n) and sublist B (every subset contains n). This easily yields the corresponding result:
S(n + 1) = S(n) + S(n) / (n + 1) + 1 / (n + 1)
Here induction kicks in. If S(n) = n, that works out to n + 1. QED.