Euler's pentagonal number theorem

Statement

The partition function satisfies the following recurrence relation:

p (n) = \sum_{k = \pm 1, \pm 2, \dots} (- 1)^{k - 1} p (n - \frac{k (3 k - 1)}{2})

for $n \geq 1$ . (note it is $0$ for $n < 0$ and $p (0) = 1$ ). Equivalently,

{(\sum_{n \geq 0} p (n) x^{n})}^{- 1} = \prod_{i \geq 1} (1 - x^{i}) = \sum_{k \in Z} (- 1)^{k} x^{k (3 k - 1) / 2}

Note that $\frac{k (3 k - 1)}{2}$ are the pentagonal numbers

Equivalence of two statements

First let us justify why the two statements are equivalent. Suppose we know that

\prod_{n \geq 1} (1 - x^{n}) = \sum_{k \in Z} (- 1)^{k} x^{k (3 k - 1) / 2}

Then, multiplying this with the generating function for the partition function yields

1 = (\sum_{n \geq 0} p (n) x^{n}) (\sum_{k \in Z} (- 1)^{k} x^{k (3 k - 1) / 2})

From this, we see that $p (0) = 1$ and for any other term $n$ , we have

p (n) = p (n - 1) - p (n - 2) + p (n - 5) + p (n - 7) - \dots

With Jacobi's Triple Product

This is a special case of Jacobi's triple product formula with $x=q^{3/2}, y {#2} = -q^{1/2}$ .

Franklin's bijective proof (1881)

Now let us proceed with the proof of the second equation in the statement.

(1 - x) (1 - x^{2}) (1 - x^{3}) (1 - x^{4}) \dots = 1 - x - x^{2} + ((- 1)^{2} - 1) x^{3} + ((- 1)^{2} - 1) x^{4} + \dots

where we note that the coefficient of each $x^{n}$ is the sum of the ways of partitioning $n$ into distinct parts times the $(- 1)$ to the power of the number of distinct parts. In other words,

= \sum_{λ ⊢ n with distinct parts} (- 1)^{number of parts of λ}

which is the (number of partitions with distinct, even number of parts) - (number of partitions with distinct, odd number of parts).

We claim that this is equal to $(- 1)^{k}$ if $n = \frac{k (3 k - 1)}{2}$ for some $k \in Z$ , otherwise it is 0. To prove this, we construct a partial involution on partitions with distinct parts that changes the parity of the number of parts.

Consider the Ferrers shape of a partition of $n$ .

Let $A$ be the set of dots on the diagonal $(y = x)$ that starts at the last dot in the first row.
Let $B$ be the set of dots in the last row.

Define the involution $τ$ as follows:

if $| A | < | B |$ , move all the dots in $A$ to the bottom to make a new row.
- Note that since it is strictly less, this creates a new, distinct part
if $| A | \geq | B |$ , move all the dots in $B$ to create a new diagonal on the right of $A$
- If the original parts were distinct, then adding one to each row will keep them distinct.

Now note that this is an involution. Let $A^{'}$ be the diagonal after applying $τ$ and let $B^{'}$ be the last row after applying $τ$ .

If we applied 1 first, then $| A^{'} | \geq | A |$ (because there must be a diagonal to the left of it that is at least as long as $A$ ) and $B^{'} = A$ , so $| A^{'} | \geq | B^{'} |$ and we are in case 2.
If we applied 2 first, then $A^{'} = B^{'}$ and $| B^{'} | > | B |$ as $B^{'}$ is another row and we have distinct parts. Thus, $| B^{'} | > | A^{'} |$ and we are in case 1.

There is one exception, and that is when $A, B$ have a common element and $| A | = | B |$ or $| A | = | B | - 1$ .

Note that we need the second part of the and: $(7, 6, 5) \mapsto (6, 5, 4, 3) \mapsto (7, 6, 5)$
Example of when $| A | = | B |$ : if we have $(7, 6, 5, 4)$ , then it's in case 2, but when we take away the bottom row, we can't put the four dots to the right of something in the last row, since the last row is now empty.
Example of when $| A | = | B | - 1$ : $(8, 7, 6, 5)$ is in case 1, but when we take the diagonal away, we are left with $4$ in the last column, and we can't have two 4's at the end.

The first case happens when the partition is of the form $λ = (2 k - 1, 2 k - 2, \dots, k)$ and so $n = \frac{k (3 k - 1)}{2}$ . In the second case, we have $λ = (2 k, 2 k - 1, \dots, k + 1)$ and $n = \frac{k (3 k + 1)}{2}$ .

Putting this together (noting that the two cases have the same parity number of parts), the original sum becomes

1 + \sum_{k \geq 1} (- 1)^{k} (x^{k (3 k - 1) / 2} + x^{k (3 k + 1) / 2})

where we have the 1 for when the partition is just $(1)$ . We notice that $\frac{- k (- 3 k + 1)}{2} = \frac{k (3 k - 1)}{2}$ so

= \sum_{k \in Z} (- 1)^{k} x^{k (3 k - 1) / 2}

as desired.

Example

Suppose we have
20260316_131602.jpg|500
Then we see that we are in case I. Applying the operation, we have
Pasted image 20260317150359.png|400
and applying $τ$ again, we have:
Pasted image 20260317150447.png|400

Here is another example, in which we are in case 2 first, and then 1:
20260316_132435.jpg|500