TAOCP 7.2.1.4 Exercise 12
A partition into distinct parts corresponds to a sequence $a_1 \ge a_2 \ge \cdots \ge a_m \ge 1$ in which all parts are distinct, so each positive integer $k$ appears at most once.
Section 7.2.1.4: Generating All Partitions
Exercise 12. ▶ [M21] [M21] (L. Euler, 1750.) Use generating functions to prove that the number of ways to partition n into distinct parts is the number of ways to partition n into odd parts. For example, 5 = 4 + 1 = 3 + 2; 5 = 3 + 1 + 1 = 1 + 1 + 1 + 1 + 1. [Note: The next two exercises use combinatorial techniques to prove extensions of this famous theorem.]
Verified: no
Solve time: 13m09s
Solution
A partition into distinct parts corresponds to a sequence $a_1 \ge a_2 \ge \cdots \ge a_m \ge 1$ in which all parts are distinct, so each positive integer $k$ appears at most once. The ordinary generating function for partitions in which part size $k$ is used at most once is therefore
$$ D(x)=\prod_{k \ge 1} (1+x^k), $$
since for each $k$ the factor $(1+x^k)$ records the choice of either omitting $k$ or including it exactly once, and multiplication corresponds to independent choices across all part sizes.
A partition into odd parts uses parts $1,3,5,\ldots$, with each odd integer allowed any nonnegative multiplicity. The generating function is therefore
$$ O(x)=\prod_{j \ge 1} \frac{1}{1-x^{2j-1}}, $$
since each odd part $2j-1$ contributes the geometric series $1 + x^{2j-1} + x^{2(2j-1)} + \cdots$.
The comparison reduces to an identity between formal power series. Each factor satisfies
$$ 1+x^k = \frac{1-x^{2k}}{1-x^k}, $$
since $(1-x^k)(1+x^k)=1-x^{2k}$. Substituting into $D(x)$ gives
$$ D(x)=\prod_{k \ge 1} \frac{1-x^{2k}}{1-x^k} = \frac{\prod_{k \ge 1}(1-x^{2k})}{\prod_{k \ge 1}(1-x^k)}. $$
The denominator factors according to even and odd indices:
$$ \prod_{k \ge 1}(1-x^k) = \left(\prod_{k \ge 1}(1-x^{2k})\right)\left(\prod_{k \ge 1}(1-x^{2k-1})\right), $$
since every positive integer is either even or odd, giving a disjoint partition of the factors.
Substituting this factorization yields
$$ D(x) = \frac{\prod_{k \ge 1}(1-x^{2k})}{\left(\prod_{k \ge 1}(1-x^{2k})\right)\left(\prod_{k \ge 1}(1-x^{2k-1})\right)} = \frac{1}{\prod_{k \ge 1}(1-x^{2k-1})} = O(x). $$
Thus the generating function for partitions into distinct parts equals the generating function for partitions into odd parts:
$$ \prod_{k \ge 1}(1+x^k) = \prod_{j \ge 1}\frac{1}{1-x^{2j-1}}. $$
Equality of formal power series implies equality of coefficients of $x^n$ for every $n \ge 0$. The coefficient of $x^n$ in $D(x)$ counts partitions of $n$ into distinct parts, and the coefficient of $x^n$ in $O(x)$ counts partitions of $n$ into odd parts, so the two counting functions coincide for all $n$.
This completes the proof. ∎