In other words,
A striking feature of this expansion is the amount of cancellation in the product. The indices 1, 2, 5, 7, 12, ... appearing on the right hand side are called pentagonal numbers (or more accurately, generalized pentagonal numbers).
The theorem can be given a combinatorial interpretation in terms of partitions. In particular, the left hand side is a generating function for the number of partitions of n into an even number of distinct parts minus the number of partitions of n into an odd number of distinct parts. (The article on unrestricted partition functions discusses this type of generating function.)
For example, the x5 coefficient is 1 because of there are two ways to split 5 into an even number of distinct parts (4+1 and 3+2), but only one way to do so for an odd number of distinct parts (5 itself).
This interpretation leads to an elegant proof of the identity via involution. Consider the Ferrers graph of any partition of n into distinct parts. For example, the diagram below shows n = 20 and the partition 20 = 7 + 6 + 4 + 3.
Let k be the number of elements in the smallest row of our graph. Let s be the number of elements in the rightmost 45 degree line of our graph (the dots which are red in the above diagram). In the diagram above, s = 2 and k = 3.
If k > s, we take the rightmost 45 degree line and move it to form a new row, as in the graph below.
If this is not the case (as in our newly formed graph where k = 2, s = 5) we reverse the process by moving the bottom row to form a new 45 degree line (in effect adding 1 element to each of the first k rows). In our case, this takes us back into the first graph.
A bit of thought shows that in fact applying this process twice brings us back to the original graph and the process always changes the parity of the number of rows. Thus this process (when it can be performed) enables us to pair off the Ferrers' graphs of partitions contributing 1 and -1 to the original sum. Everything cancels, UNLESS there are some cases where our operation cannot be performed. In fact, there are two of them.
1) k = s and the rightmost diagonal and bottom row meet. For example,
Attempting to perform the operation would lead us to:
which fails to change the parity of the number of rows, and is not reversible in the sense that performing the operation again does not take us back to the original graph. If there are k elements in the last row of the original graph, then
2) k = s+1 and the rightmost diagonal and bottom row meet. For example,
Our operation requires us to move the right diagonal to the bottom row, but that would lead to two rows of 3 elements, forbidden since we're counting partitions into distinct parts. This is the previous case but with one fewer row, so
where m=1-k (which is negative).
In summary, we have shown that partitions into an even number of distinct parts and an odd number of distinct parts exactly cancel each other out, except for pentagonal numbers, where there is exactly one case left over (which contributes a factor of (-1)k). But this is precisely what the right side of the identity says should happen, so we are finished.
This gives a beautiful recurrence for calculating , the number of partitions of n Partition function (number theory).
or more formally,
where the summation is over all (including negative) i and is the pentagonal number calculated as above.
Another way of proving the identity is by observing its implications on certain sets of partitions. Start by noting that is the exact inverse (in terms of formal power series) of the well known generating function for the partiton function p(n), . This means that
where an is the coefficient of xn in the expansion of our product. We thus have a0 p(0) = a0 = 1 and for all (which, of course, is a recurrence relation that defines the ai uniquely). It is now easy to find an equivalence to our identity in terms of sets of partitions. Indeed, if we are to find
which transcribes in terms of sets of partitions as the fact that the sets
is actually an involution (and thus in particular a bijection), which proves our claim and the identity.
Here is a simple Python program which computes partitions using the Pentagonal number theorem.
pentagonal = lambda n : n*(3*n-1)/2
def generalised_pentagonal(n): # 0, 1, -1, 2, -2
if n < 0: return 0
if n%2 == 0: return pentagonal(n/2+1)
else: return pentagonal(-(n/2+1))
pt = 
for n in range (1, 1000+1):
r = 0
f = -1
i = 0
while generalised_pentagonal(i) <= n:
k = generalised_pentagonal(i)
if k > n:
if i%2==0: f = -f
r += f*pt[n - k]
i += 1