Generating Functions - Applications

Euler's Partition Theorem demonstrates the power of generating functions to reveal deep identities by transforming combinatorial statements into equations between power series.

Proof using Generating Functions:

Let $O(x)$ be the generating function for partitions into odd parts, and $D(x)$ be the generating function for partitions into distinct parts.

Partitions into odd parts: $O(x) = \prod_{k=0}^{\infty} \frac{1}{1-x^{2k+1}}$

The factor $\frac{1}{1-x^{2k+1}} = 1 + x^{2k+1} + x^{2(2k+1)} + x^{3(2k+1)} + \cdots$ represents using 0, 1, 2, ... parts of size $2k+1$ (odd).

Partitions into distinct parts: $D(x) = \prod_{k=1}^{\infty} (1 + x^k)$

The factor $(1 + x^k)$ represents either not using or using exactly one part of size $k$ (distinct).

To prove: $O(x) = D(x)$.

We use a clever algebraic identity. For any $k \geq 0$: $(1 + x^{2k+1})(1 + x^{2(2k+1)})(1 + x^{4(2k+1)})(1 + x^{8(2k+1)})\cdots$

This product (using powers of 2) can be rewritten. Each term $1 + x^{2^j(2k+1)}$ contributes either 0 or 1 copy of size $2^j(2k+1)$. Any positive integer can be uniquely written in binary as $\sum_{j} \epsilon_j 2^j$ where $\epsilon_j \in \{0,1\}$, so: $(1 + x^{2k+1})(1 + x^{2(2k+1)})(1 + x^{4(2k+1)})\cdots = 1 + x^{2k+1} + x^{2(2k+1)} + x^{3(2k+1)} + \cdots = \frac{1}{1-x^{2k+1}}$

Therefore, for each odd number $2k+1$, the product of $(1 + x^m)$ for all $m$ that are powers of 2 times $2k+1$ equals $\frac{1}{1-x^{2k+1}}$.

Taking the product over all odd numbers $2k+1$: $D(x) = \prod_{k=1}^{\infty} (1 + x^k) = \prod_{k=0}^{\infty} \left[\prod_{j=0}^{\infty} (1 + x^{2^j(2k+1)})\right] = \prod_{k=0}^{\infty} \frac{1}{1-x^{2k+1}} = O(x)$

This completes the proof. $\square$