Problem on number of ways of writing $n$ as a sum of distinct integers vs a sum of odd integers 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. 
 A: 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$$
A: 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|$.
