Problem
COM-B2-M09-P017 Distinct Parts and Odd Parts
Prove that for every \(n\), the number of partitions of \(n\) into distinct parts equals the number of partitions of \(n\) into odd parts.
Write the generating functions for the two types of partitions and transform \((1+x^i)\).
Partitions into distinct parts are encoded by \(\prod_{i\ge 1}(1+x^i)\), because each part \(i\) may be taken at most once. Use \(1+x^i=\frac{1-x^{2i}}{1-x^i}\):
\[\prod_{i\ge 1}(1+x^i)=\frac{\prod_{i\ge 1}(1-x^{2i})}{\prod_{i\ge 1}(1-x^i)}.\]
The denominator contains factors for all positive \(i\), while the numerator cancels all even factors. What remains is \(\prod_{j\ge 1}\frac{1}{1-x^{2j-1}}\), the generating function for partitions into odd parts. Therefore the coefficients of \(x^n\) are equal.
A classical result; for a first encounter, the formal proof at coefficient level is sufficient.