Pentagonal Number Theorem - Partition Recurrence

Partition Recurrence

We can rephrase the above proof, using partitions, which we denote as:, where . The number of partitions of n is the partition function p(n) having generating function:

Note that is the reciprocal of the product on the left hand side of our identity:

$\left( \sum_{n=0}^\infty p(n) x^n \right) \cdot \left(\prod_{n=1}^\infty (1-x^n)\right) = 1$

Let us denote the expansion of our product by, so that

Multiplying out the left hand side and equating coefficients on the two sides, we obtain a₀ p(0) = 1 and for all . This gives a recurrence relation defining p(n) in terms of a_n, and vice versa a recurrence for a_n in terms of p(n). Thus, our desired result:

$a_i := \begin{cases}1 & \mbox{ if } i = \frac{1}{2}(3k^2 \pm k) \mbox{ and } k \mbox{ is even}\\ -1 & \mbox{ if } i = \frac{1}{2}(3k^2 \pm k) \mbox{ and } k \mbox{ is odd }\\ 0 & \mbox{ otherwise }\end{cases}$

for is equivalent to the identity where and i ranges over all integers such that (this range includes both positive and negative i, so as to use both kinds of generalized pentagonal numbers). This in turn means:

In terms of sets of partitions, this is equivalent to saying that the following sets are of equal cardinality:

and ,

where denotes the set of all partitions of . All that remains is to give a bijection from one set to the other, which is accomplished by the function φ from X to Y which maps the partition to the partiton defined by:

$\varphi(\lambda) := \begin{cases} \lambda' : n - g_{i-1} = (\ell + 3i -1) + (\lambda_1 - 1) + \dotsb + (\lambda_\ell - 1) &\mbox{ if } \ell+3i \geq \lambda_1\\ \\ \lambda' : n - g_{i+1} = (\lambda_2 + 1) + \dotsb + (\lambda_\ell + 1) + \underbrace{1+\dotsb+1}_{\lambda_1 - \ell - 3i - 1} &\mbox{ if } \ell+3i < \lambda_1 \end{cases}$ .

This is an involution (a self-inverse mapping), and thus in particular a bijection, which proves our claim and the identity.

Read more about this topic: Pentagonal Number Theorem

Famous quotes containing the word recurrence:

“Forgetfulness is necessary to remembrance. Ideas are retained by renovation of that impression which time is always wearing away, and which new images are striving to obliterate. If useless thoughts could be expelled from the mind, all the valuable parts of our knowledge would more frequently recur, and every recurrence would reinstate them in their former place.”
—Samuel Johnson (1709–1784)