A Mathematical Gem from Euler
By Dr. Hassan Shirvani–The Swiss mathematician Leonhard Euler (1707–1783) is widely considered as one of the greatest mathematicians who ever lived. He made fundamental and path-breaking contributions to many areas of mathematics and physics. In the following example, Euler displays the inspired ease with which he managed to crack some of the most difficult mathematical problems of his time, often to the great amazement of his contemporaries.
The Distinct/Odd Partitions Problem
In 1740, Euler was sent a problem that had long puzzled many mathematicians in Europe. This was the famous distinct/odd partitions problem. Suppose we take an arbitrary natural number such as 5. This number can be partitioned into (written as the sum of) other distinct natural numbers in several ways. For example, we can write 5 as the sum of 5 alone, or as the sum of 4 and 1, or as the sum of 3 and 2. (Of course, we can also write 5 as the sum of, say, 3 and 1 and 1, but this is not acceptable, since the last two numbers are not distinct). This means that number 5 has only three distinct partitions. Likewise, number 6 can be distinctly partitioned as 6, 5 + 1, 4 + 2, and 3 + 2 + 1. Thus, number 6 has four distinct partitions. In the following table we show the number of distinct partitions for the first few natural numbers:
N = Number 0 1 2 3 4 5 6.……13
D(N) = Number of distinct partitions 1 1 1 2 2 3 4……18
Note that by convention D(0) is set equal to 1.
Let us now consider a different type of partitioning number 5, in which 5 is again broken into smaller natural numbers, except that these smaller numbers are all odds now, with repetitions allowed. Under these conditions, the only acceptable odd partitions for number 5 are 5, 3 + 1 + 1, and 1 + 1 + 1+1 +1. In other words, the number of acceptable odd partitions for number 5 is also three. In the following table we again show the number of acceptable odd partitions for the first few natural numbers:
N = Number 0 1 2 3 4 5 6….…13
O(N) = Number of odd partitions 1 1 1 2 2 3 4 ……18
Again by convention O(0) is set equal to 1.
As the above tables show, the numbers of distinct and odd partitions are the same for all the natural numbers between 1 and 13. Mathematicians in Europe wanted to know whether this result was just a fluke or that it was also true for all other natural numbers. Having given up on finding an answer to this question, they asked Euler for help, who famously resolved the issue in just one evening. He showed that indeed D(N) = O(N) for all N.
The Solution
As a first step, Euler realized that writing any number as the sum of smaller numbers is like writing any power of a variable, say x, into the product of smaller powers. For example, if it is true that number 5 can be written as either 4 +1 or 3 +2, then it must also be true that x5 can be written as either x4. x1 or x3 . x2. This is because powers add up in any multiplication with the same base. Thus, instead of counting the number of ways in which any number can be written as the sum of smaller numbers, we can count the number of ways in which any power of a variable can be written as the product of smaller powers. Next, Euler defines the following generating function:
f(x) = (1 + x)(1 + x2)(1 + x3)………
which can be also written as:
f(x) = 1 + x + x2 + (x3 + x2.x1) + (x4 + x3x1) + ……
Clearly, the fourth item on the right hand side of the above function shows the number of distinct partitions of number 3, while the fifth item shows the number of distinct partitions of number 4, etc. Thus, we have:
f(x) = 1 + x + x2 + 2x3 + 2x4 + 3x5 +……..+ 18x13 + ….
In other words, the coefficients of the power series of the above function will give us all the D numbers in the first table.
As a next step, Euler defines a second generating function as:
g(x) = (1/1-x)(1/1-x3)(1/1-x5)………
which can be also be written as:
g(x) = (1 + x + x2 + ….)(1 + x3 + x6 +….)(1 + x5 + x10+….)( ……..
or,
g(x) = 1 + x + x2 + (x3 + x1.x1.x1) + (x3x1 + x1.x1.x1.x1) + ……..
whose coefficients again indicate the number of odd partitions for various natural numbers. That is:
g(x) = 1 + x + x2 + 2x3 + 2x4 + 3x5 +……..+ 18x13 + ……..
To complete the proof that the pairwise coefficients of the power series of the two respective generating functions are equal, that is to show that D(N) = O(N) for all N, Euler then proceeds to show that f and g are indeed the same generating function. This is done by some manipulations as follows:
g(x) = (1/1-x)[1-x2/1-x2](1-x3)[1-x4/1-x4]……
where any fraction inside [ ] is equal to one. The above function can be rewritten as:
g(x) = (1/1-x)[(1 – x)(1 + x)/1-x2](1-x3)[(1 – x2)(1 + x2)/1 – x4]……
which can be converted into the following equivalent form:
g(x) = (1 + x)(1 + x2)(1 + x3)………
This, of course, is the same as f(x). Thus, Euler was able to successfully resolve one of the great unsolved problems of the 18th century European mathematics.
Hassan Shirvani, Ph.D.
Professor Cullen Foundation Chair in Economics