Problem on number of ways of writing $n$ as a sum of distinct integers vs a sum of odd integers

Question

I found this problem while doing a few problems on partitions of an integer:

Prove that the number of ways of writing $n$ as a sum of distinct positive integers is equal to the number of ways of writing $n$ as a sum of odd positive integers.

Attempt at solution: I tried to perform some manipulations on the generating function for the partitions of $n$ to get the latter, but could not do so.

Answer 1

I think this was proved by Euler.

The number of partitions of $n$ as a sum of odd positive integers is the coefficient of the $x^n$ in the expansion of : $$\frac{1}{(1-x)(1-x^3)(1-x^5)(1-x^7)\dots} $$

and the number of ways of writing $n$ as a sum of distinct positive integers is the coefficient of $x^n$ in

$$(1+x)(1+x^2)(1+x^3)\dots$$

Trivially we have $\frac{1}{(1-x)(1-x^3)(1-x^5)(1-x^7)\dots} = \frac{1-x^2}{1-x} \cdot \frac{1-x^4}{1-x^2} \cdot \frac{1-x^6}{1-x^3} \cdot \frac{1-x^8}{1-x^4}\dots$ $$ = (1+x)(1+x^2)(1+x^3)\dots$$

Answer 2

First note that any positive integer $k$ has a unique representation $k=op$ where $o$ is odd and $p$ is a power of 2, namely where $o$ is $k$'s largest odd factor and $p$ is $k$'s largest factor that is a power of 2.

Moreover, any positive integer $m$ has a unique binary representation and thus a unique decomposition (aside from permutation of the terms) as the sum of distinct powers of 2.

Let $\mathscr{P}_D$ be the set of partitions of $n$ into distinct positive integers, and $\mathscr{P}_O$ be the set of partitions of $n$ into odd parts.

For each partition $D\in \mathscr{P}_D$, let $f(D)$ be a partition into odd integers obtained as follows. For each part $k$ of $D$, let $k=op$ where $o$ is odd and $p$ is a power of 2. Replace this part $k$ by $p$ parts, each of size $o$. The resulting partition is $f(D)$. By construction, it is a partition into odd parts.

Suppose $D_1$, $D_2$ are two different partitions of $n$ into distinct positive integers. Then there is some part size $k=op$ where, wlog, $D_1$ has a part of size $k$ and $D_2$ does not. Then $f(D_i)$ has $m_i$ parts of size $o$ where $m_1$'s decomposition as the sum of distinct powers of 2 contains $p$ and $m_2$'s does not. Thus $m_1\ne m_2$, so $f(D_1)\ne f(D_2)$. Thus $f$ is injective, so $|\mathscr{P}_D|\le|\mathscr{P}_O|$.

For each partition $O\in \mathscr{P}_O$, let $g(O)$ be a partition into distinct integers, obtained as follows. For each odd integer $o$ which is the size of any parts of $O$, let there be $m$ parts of size $o$. Express $m$ as the sum of distinct powers of 2: $$m=\sum_{i\in I} 2^i$$ Then for each $i$ replace $2^i$ parts of size $o$ by one part of size $2^io$. For any $o$ the $2^io$ are distinct because the $2^i$ were distinct by construction. And parts arising from different $o$ cannot have the same size $k$ because $k$ has only one representation as the product of an odd integer and a power of 2.

Suppose $O_1$, $O_2$ are two different partitions of $n$ into odd parts. Then there is some part size $o$ where $O_i$ has $m_i$ parts of size $o$, and $m_1\ne m_2$. Then $m_1$ and $m_2$ do not have the same decomposition as the sum of distinct powers of 2. So there is some $i$ where $2^i$ is in the one but not the other, and therefore a part of size $2^io$ is in one of the $g(O_i)$ but not the other. Thus $g(O_1)\ne g(O_2)$, so $g$ is injective, so $|\mathscr{P}_O|\le|\mathscr{P}_D|$.

Putting the two results together, $|\mathscr{P}_D|=|\mathscr{P}_O|$.