TAOCP 5.1.1 Exercise 16
The exercise as printed contains two typographical errors: 1.
Exercise 16. [M25] (1, Euler.) Prove the following identities by interpreting both sides of the equations in terms of partitions:
$$\prod_{k \ge 0} \frac{1}{(1-q^{2^k})} = \frac{1}{(1-z)(1-q)(1-q^2)\ldots}$$
$$= 1 + \frac{z}{1-q} + \frac{z^2}{(1-q)(1-q^2)} + \cdots = \sum_{n \ge 0} z^n \Big/ \prod_{k=1}^n (1-q^k).$$
$$\prod_{k \ge 0} (1 + q^{2^k} z) = (1+z)(1+qz)(1+q^2 z)\ldots$$
$$= 1 + \frac{z}{1-q} + \frac{z^2 q}{(1-q)(1-q^2)} + \cdots = \sum_{n \ge 0} z^n q^{n(n-1)/2} \Big/ \prod_{k=1}^n (1-q^k).$$
Verified: yes
Solve time: 23m53s
The exercise as printed contains two typographical errors:
- In the products, the exponents are written as (q^{2^k}) instead of (q^k).
- The first chain of equalities includes an extraneous middle expression (\frac{1}{(1-z)(1-q)(1-q^2)\cdots}) that does not equal the other expressions.
The intended identities are Euler’s (q)-binomial theorems:
[ \prod_{k=0}^{\infty} \frac{1}{1 - z q^{k}} = \sum_{n=0}^{\infty} \frac{z^{n}}{\prod_{k=1}^{n} (1 - q^{k})}, \qquad \prod_{k=0}^{\infty} (1 + z q^{k}) = \sum_{n=0}^{\infty} \frac{z^{n} q^{n(n-1)/2}}{\prod_{k=1}^{n} (1 - q^{k})}. ]
We prove both by constructing explicit bijections between the partitions enumerated by each side.
First Identity
[ \prod_{k=0}^{\infty} \frac{1}{1 - z q^{k}} = \sum_{n=0}^{\infty} \frac{z^{n}}{\prod_{k=1}^{n} (1 - q^{k})}. ]
Interpretation of the left‑hand side.
Expanding each factor as a geometric series,
[
\frac{1}{1 - z q^{k}} = \sum_{m_k \ge 0} (z q^{k})^{m_k} = \sum_{m_k \ge 0} z^{m_k} q^{k m_k}.
]
A term in the product corresponds to choosing a multiplicity (m_k \ge 0) for every nonnegative integer (k). The exponent of (z) is (\sum_k m_k), the total number of elements (counting repetitions); the exponent of (q) is (\sum_k k m_k), the sum of the elements. Thus the left‑hand side is the generating function for multisets of nonnegative integers (zeros allowed), where (z) marks the cardinality and (q) marks the sum.
Interpretation of the right‑hand side.
For a fixed (n \ge 0), the factor
[
\frac{1}{\prod_{k=1}^{n} (1 - q^{k})}
]
is the generating function for partitions whose parts are at most (n) (equivalently, partitions into at most (n) parts). The term (z^n) marks the parameter (n). Hence the right‑hand side is
[
\sum_{n \ge 0} z^n \sum_{\mu: \text{parts}(\mu) \le n} q^{|\mu|}.
]
Bijection (conjugation of Ferrers diagrams).
Take a multiset generated by the left‑hand side with exactly (n) elements (some possibly zero). Write its elements in non‑increasing order:
[
\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n \ge 0.
]
This is a partition with exactly (n) parts (zeros allowed). Its Ferrers diagram has (n) rows. The conjugate partition (\lambda') has (\lambda_1) rows, and because the original diagram has only (n) rows, each row of (\lambda') has length at most (n). Hence (\lambda') is a partition with parts (\le n). Conjugation preserves the sum, so (|\lambda'| = |\lambda|).
Conversely, any partition (\mu) with parts (\le n) can be padded with zeros to obtain a partition with exactly (n) parts (allowing zeros); its conjugate then has exactly (n) rows and yields the original multiset. This gives a bijection [ {\text{multisets of size } n \text{ with sum } S} ;\longleftrightarrow; {\text{partitions with parts } \le n \text{ and sum } S}. ]
Under this bijection, the cardinality (n) of the multiset becomes the summation index (n) on the right, and the sum (S) is preserved. Therefore the coefficient of (z^n) on the left equals the generating function for partitions with parts (\le n), namely (1 / \prod_{k=1}^n (1 - q^k)). Summing over (n \ge 0) proves the identity.
Second Identity
[ \prod_{k=0}^{\infty} (1 + z q^{k}) = \sum_{n=0}^{\infty} \frac{z^{n} q^{n(n-1)/2}}{\prod_{k=1}^{n} (1 - q^{k})}. ]
Interpretation of the left‑hand side.
Expanding the product, each factor ((1 + z q^{k})) contributes either (1) (the part (k) is not used) or (z q^{k}) (the part (k) is used exactly once). Hence the left‑hand side generates all sets of distinct nonnegative integers (zeros allowed at most once), where (z) marks the cardinality and (q) marks the sum:
[
\sum_{\substack{\lambda \text{ distinct parts} \ \lambda_i \ge 0}} z^{\ell(\lambda)} q^{|\lambda|}.
]
Interpretation of the right‑hand side.
For a fixed (n \ge 0), the term
[
\frac{z^{n} q^{n(n-1)/2}}{\prod_{k=1}^{n} (1 - q^{k})}
]
is (z^n q^{n(n-1)/2}) times the generating function for partitions with parts at most (n).
Bijection (staircase removal).
Let (\lambda) be a set of (n) distinct nonnegative integers. Write its elements in strictly decreasing order:
[
\lambda_1 > \lambda_2 > \dots > \lambda_n \ge 0.
]
Define a new sequence (b_i = \lambda_i - (n-i)) for (i = 1, \dots, n). Because the (\lambda_i) decrease by at least (1), we have
[
b_1 \ge b_2 \ge \dots \ge b_n \ge 0,
]
so ((b_1, \dots, b_n)) is a partition into at most (n) parts (allowing zeros). By conjugation, this corresponds to a partition with parts (\le n). The sum of the (b_i) is
[
\sum_{i=1}^{n} b_i = \sum_{i=1}^{n} \lambda_i - \sum_{i=1}^{n} (n-i) = |\lambda| - \frac{n(n-1)}{2}.
]
Conversely, given a partition (\mu) with parts (\le n), write it as a non‑increasing sequence (b_1 \ge b_2 \ge \dots \ge b_n \ge 0) by appending zeros if necessary. Define (\lambda_i = b_i + (n-i)). Then (\lambda_1 > \lambda_2 > \dots > \lambda_n \ge 0) are distinct nonnegative integers, and [ |\lambda| = |\mu| + \frac{n(n-1)}{2}. ] The number of parts of (\lambda) is exactly (n).
This transformation is a bijection between (n)-element sets of distinct nonnegative integers and partitions with parts (\le n). It preserves the number of parts (n) and increases the sum by (n(n-1)/2). Hence the generating function for (n)-element sets of distinct nonnegative integers is [ z^{n} q^{n(n-1)/2} \cdot \frac{1}{\prod_{k=1}^{n} (1 - q^{k})}. ] Summing over (n \ge 0) yields the right‑hand side.
Both identities are now proved by combinatorial interpretations and explicit bijections. ∎