Eulerの分割恒等式

方針：ex-eup-three-factors の計算を、因子が $N$ 個の場合に行う。打ち消し合いのあと、$N$ 次以下では両辺の無限積と同じになることを確かめる。
段 1（1 つの因子の書き換え）：$k\ge1$ について $(1-x^k)(1+x^k)=1-x^{2k}$ であり、$1-x^k$ は定数項が $1$ なので逆数をもつ。よって $1+x^k=\frac{1-x^{2k}}{1-x^k}$ である。
段 2（$N$ 個の積）：$N\ge1$ を固定する。段 1 を $k=1,\dots,N$ で使って掛けると
$$ \prod_{k=1}^N(1+x^k)=\frac{\prod_{k=1}^N(1-x^{2k})}{\prod_{k=1}^N(1-x^k)} $$
である。分子は $1-x^j$（$j=2,4,\dots,2N$）の積、分母は $1-x^j$（$j=1,2,\dots,N$）の積である。
段 3（打ち消し合い）：$N$ 以下の偶数 $j$ の因子 $1-x^j$ は分子にも分母にもあるので、打ち消し合う。分子には $N< j\le2N$ の偶数 $j$ の因子が、分母には $N$ 以下の奇数 $j$ の因子が残る：
$$ \prod_{k=1}^N(1+x^k)=\frac{\prod_{N< j\le2N,\ j\text{ 偶数}}(1-x^j)}{\prod_{j\le N,\ j\text{ 奇数}}(1-x^j)}. $$
段 4（$N$ 次以下で比べる）：残った分子の因子 $1-x^j$ は $j>N$ なので $\equiv1\pmod{x^{N+1}}$ であり、準備の 2 により分子全体も $\equiv1$ である。よって
$$ \prod_{k=1}^N(1+x^k)\equiv\prod_{j\le N,\ j\text{ 奇数}}\frac1{1-x^j}\pmod{x^{N+1}} $$
である。
段 5（無限積に戻す）：左辺の無限積 $\prod_{k\ge1}(1+x^k)$ の因子を $1+G_k$（$G_k=x^k$）と書くと、$\operatorname{ord}G_k\le N$ となるのは $k\le N$ のものだけなので、準備の 1 により、無限積は $N$ 次以下で $\prod_{k=1}^N(1+x^k)$ と一致する。右辺の無限積 $\prod_{j\text{ 奇数}}\frac1{1-x^j}$ の因子も $\frac1{1-x^j}=1+H_j$（$H_j=x^j+x^{2j}+\cdots$）と書くと、$\frac1{1-x^j}-1=H_j$ の位数は $j$ なので、同じ理由で、$N$ 次以下で $\prod_{j\le N,\ j\text{ 奇数}}\frac1{1-x^j}$ と一致する。段 4 と合わせて、2 つの無限積は $N$ 次以下で一致する。$N$ は任意なので、2 つの無限積は等しい。
段 6（後半）：準備の 3 で見たとおり、左辺の $x^n$ の係数は $D(n)$、右辺の $x^n$ の係数は $O(n)$ である。等しい級数の係数は等しいので $D(n)=O(n)$ である。$\square$

方針：存在は「2 で割れるだけ割る」ことで示し、ただ 1 通りであることは素因数 2 の個数を比べて示す。
段 1（存在）：$d$ が奇数なら $e=0$、$j=d$ でよい。偶数なら $2$ で割る。割った結果がまだ偶数ならまた $2$ で割る。割るたびに数は小さくなる正の整数なので、この操作は有限回で終わり、最後に奇数 $j$ が残る。割った回数を $e$ とすると $d=2^ej$ である。
段 2（ただ 1 通り）：$2^ej=2^{e'}j'$（$j,j'$ は奇数）で $e< e'$ とすると、両辺を $2^e$ で割って $j=2^{e'-e}j'$ となり、右辺は偶数、左辺は奇数で矛盾する。$e>e'$ でも同様である。よって $e=e'$ であり、両辺を $2^e$ で割って $j=j'$ である。$\square$

方針：$\Phi$ の結果が本当に「部分が相異なる分割」になること、$\Psi$ の結果が「部分がすべて奇数の分割」になることを確かめ、続けて行うと元に戻ることを示す。
段 1（$\Phi$ の結果はただ 1 つに決まり、和を変えない）：$m$ を相異なる 2 の冪の和で表す方法はただ 1 通りである（分割の母関数の 2 進展開の一意性）。よって置き換えは 1 通りに決まる。置き換えた部分の和は $(2^{a_1}+\cdots+2^{a_r})j=mj$ で、元の $m$ 個の $j$ の和に等しい。したがって $\Phi$ の結果も $n$ の分割である。
段 2（$\Phi$ の結果の部分は相異なる）：$\Phi$ の結果の部分はすべて $2^aj$（$j$ 奇数）の形で、同じ $j$ からは相異なる $a$ しか出てこない。異なる奇数 $j\ne j'$ から出た部分 $2^aj$ と $2^{a'}j'$ は、lem-eup-odd-part の一意性により等しくない。よって部分は相異なる。
段 3（$\Psi$ の結果は奇数の部分の分割）：$\Psi$ は各部分 $d=2^ej$ を $2^e$ 個の $j$ に替えるので、和は $2^ej=d$ で変わらず、現れる部分は奇数 $j$ だけである。
段 4（$\Psi\circ\Phi$ は元に戻る）：奇数の部分の分割で、$j$ が $m$ 回現れるとする。$\Phi$ で $2^{a_1}j,\dots,2^{a_r}j$ になり、$\Psi$ でそれぞれ $2^{a_1}$ 個、…、$2^{a_r}$ 個の $j$ に戻る。合計 $2^{a_1}+\cdots+2^{a_r}=m$ 個の $j$ なので、元の分割に戻る。
段 5（$\Phi\circ\Psi$ は元に戻る）：相異なる部分の分割で、奇数 $j$ に対して $2^ej$ の形の部分が $2^{e_1}j,\dots,2^{e_r}j$（$e_1>\cdots>e_r$、部分が相異なるので $e_i$ も相異なる）だとする。$\Psi$ で $j$ が $m:=2^{e_1}+\cdots+2^{e_r}$ 個になる。$\Phi$ は $m$ を相異なる 2 の冪の和で表すが、その表し方はただ 1 通りなので $2^{e_1}+\cdots+2^{e_r}$ そのものであり、部分 $2^{e_1}j,\dots,2^{e_r}j$ に戻る。
段 6（結論）：段 4・段 5 により $\Phi$ と $\Psi$ は互いに逆なので、$\Phi$ は 1 対 1 の対応であり、2 種類の分割の個数は等しい。$\square$