Proof of Euler's partition theorem by Glaisher's bijection

Proof

We build a bijection, due to Glaisher, between the two sets of partitions.

1. A partition of $n$ is determined by its multiplicity function $\mu : \Z_{>0} \to \N$. Here $\mu(k)$ is the number of parts equal to $k$. It has finite support and $\sum_k k\, \mu(k) = n$.
2. Conversely, each such function with finite support and $\sum_k k\, \mu(k) = n$ is the multiplicity function of exactly one partition of $n$.
3. Let $\mathcal{O}$ be the set of these $\mu$ with $\mu(k) = 0$ for every even $k$. These are the partitions of $n$ into odd parts.
4. Let $\mathcal{D}$ be the set of these $\mu$ with $\mu(k) \le 1$ for every $k$. These are the partitions of $n$ into distinct parts.
5. Fact A: each positive integer $d$ is $2^a m$ for exactly one pair $(a, m)$ with $a \in \N$ and $m$ odd.
6. Proof of Fact A. Let $a$ be the largest natural number with $2^a \mid d$; it exists because $2^a \le d$. Then $m = d / 2^a$ is odd, otherwise $2^{a+1} \mid d$.
7. If $2^a m = 2^b m'$ with $m, m'$ odd and $a < b$, then $m = 2^{b-a} m'$ is even, a contradiction. So $a = b$, and then $m = m'$.
8. Fact B: each $k \in \N$ is $\sum_{a \in B} 2^a$ for exactly one finite set $B \subseteq \N$. We call $B$ the binary set of $k$. We use strong induction on $k$.
9. For $k = 0$ the only such set is $B = \varnothing$, because a nonempty $B$ gives a positive sum.
10. Let $k \ge 1$. In $\sum_{a \in B} 2^a$ all terms with $a \ge 1$ are even. So $0 \in B$ exactly when $k$ is odd.
11. Let $\varepsilon = 1$ if $k$ is odd and $\varepsilon = 0$ otherwise, and let $k' = (k - \varepsilon)/2 < k$.
12. Then $k = \sum_{a \in B} 2^a$ holds if and only if $0 \in B \Leftrightarrow \varepsilon = 1$ and $k' = \sum_{a \in B, a \ge 1} 2^{a-1}$.
13. By the induction hypothesis, $k'$ has exactly one binary set $B'$. So $B = \{a + 1 : a \in B'\}$, together with $0$ when $\varepsilon = 1$, is the only binary set of $k$.
14. Define $\Phi : \mathcal{O} \to \mathcal{D}$. For $\mu \in \mathcal{O}$ and odd $m$, let $B_m$ be the binary set of $\mu(m)$.
15. For $d = 2^a m$ as in Fact A, put $\nu(d) = 1$ if $a \in B_m$, and $\nu(d) = 0$ otherwise. Let $\Phi(\mu) = \nu$.
16. The support of $\nu$ is finite, because only finitely many $m$ have $\mu(m) > 0$ and each $B_m$ is finite.
17. We have $\sum_d d\, \nu(d) = \sum_{m \text{ odd}} m \sum_{a \in B_m} 2^a = \sum_{m \text{ odd}} m\, \mu(m) = n$, by Fact A. So $\nu \in \mathcal{D}$.
18. Define $\Psi : \mathcal{D} \to \mathcal{O}$. For $\nu \in \mathcal{D}$ and odd $m$, let $\mu(m) = \sum_{a \in A_m} 2^a$, where $A_m = \{a \in \N : \nu(2^a m) = 1\}$. Let $\mu(k) = 0$ for even $k$.
19. Each $A_m$ is finite, and only finitely many $A_m$ are nonempty, because $\nu$ has finite support. So $\mu$ has finite support.
20. By Fact A, $\sum_k k\, \mu(k) = \sum_{m \text{ odd}} \sum_{a \in A_m} 2^a m = \sum_d d\, \nu(d) = n$. So $\Psi(\nu) = \mu \in \mathcal{O}$.
21. Let $\mu \in \mathcal{O}$ and $\nu = \Phi(\mu)$. Then $A_m = B_m$ for each odd $m$, so $\Psi(\nu)(m) = \sum_{a \in B_m} 2^a = \mu(m)$. Thus $\Psi \circ \Phi$ is the identity.
22. Let $\nu \in \mathcal{D}$ and $\mu = \Psi(\nu)$. By Fact B, the binary set of $\mu(m)$ is $A_m$. So $\Phi(\mu)(2^a m) = 1$ exactly when $a \in A_m$, that is, when $\nu(2^a m) = 1$.
23. By Fact A every $d \ge 1$ has the form $2^a m$, so $\Phi(\mu) = \nu$. Thus $\Phi \circ \Psi$ is the identity.
24. A map with a two-sided inverse is a bijection. So $\Phi$ is a bijection from $\mathcal{O}$ to $\mathcal{D}$.
25. Both sets are finite, since there are finitely many partitions of $n$. By the bijection principle, $\abs{\mathcal{O}} = \abs{\mathcal{D}}$.