Euler's theorem. For any natural number N, the number of bags of (not necessarily distinct) odd natural nubers whose sum is N equals the number of sets of (distinct) positive integers whose sum is N.
Proof. In this proof:
| i's | stand for positive integers, |
| q's | stand for odd natural numbers, and |
| t's | stand for powers of 2. |
Euler's theorem follows from a 1-1 correspondence between bags of q's and sets of i's with the same sum.
In order to construct the bag of q's corresponding to a given set of i's, we observe that for each i the factorization i=t•q is unique, For each i in the set we put, with i=t•q, t instances of q into the bag. The result is a bag of q's with the same sum.
In order to construct the set of i's corresponding to a given bag of q's, we observe that each natural f is uniquely the sum of distinct t's. For a q with f occurrences in the bag we put into the set the i's of the form t•q for those distinct t's whose sum equals f. The result is a set of (distinct) i's
with the same sum.
Grouping the i's in the set by largest odd divisor we see that the two transformations are each other's inverse. (End of Proof).
I found the above proof shortly after I had firmly decided to discard Ferrer diagrams and similar pictorial "aids". I asked myself how I could derive simply a bag of q's in a sum-preserving manner from a given set of i's. Since I was heading for a bag (in which multiple occurrences are allowed) I investigated how I could transform in a sum-preserving manner the individual i's into bags of q's. With the above result.
| Plataanstraat 5 5671 AL NUENEN The Netherlands |
27 April 1981 prof.dr. Edsger W. Dijkstra Burroughs Research Fellow |
P.S. By distributing the above I learned that the proof is already known.
Last revised on Sun, 13 Jul 2003.