Proof of the generating function for partitions

Proof

We compute the coefficients of the finite partial products, and we show that they stabilise at $p(n)$.

1. All series are formal power series in $\Z[\![x]\!]$. For $k \ge 1$ let $g_k = \sum_{m \ge 0} x^{km}$. So $[x^j] g_k = 1$ if $k \mid j$, and $[x^j] g_k = 0$ otherwise.
2. By the product formula, $[x^n](x^k g_k) = [x^{n-k}] g_k$ for $n \ge k$, and $0$ for $n < k$. So $x^k g_k = \sum_{m \ge 1} x^{km}$.
3. Hence $(1 - x^k) g_k = g_k - x^k g_k = 1$. So $1 - x^k$ is a unit and $\frac{1}{1 - x^k} = g_k$.
4. For $N \in \N$ let $P_N = g_1 g_2 \cdots g_N$, with $P_0 = 1$. The infinite product $\prod_{k \ge 1} \frac{1}{1 - x^k}$ means the series whose coefficient of $x^n$ is $[x^n] P_N$ for all $N \ge n$.
5. Steps 6 to 13 show that this is well defined, and compute it. Let $c_N(n)$ be the number of tuples $(m_1, \dots, m_N) \in \N^N$ with $\sum_{k=1}^{N} k\, m_k = n$.
6. Claim: $[x^n] P_N = c_N(n)$ for all $N, n \in \N$. We argue by induction on $N$.
7. For $N = 0$, $P_0 = 1$ has $[x^n] P_0 = 1$ if $n = 0$ and $0$ otherwise. Only the empty tuple has length $0$, and its sum is $0$. So $c_0(n) = [x^n] P_0$.
8. Let $N \ge 1$. By the product formula and step 1, $[x^n] P_N = \sum_{i + j = n} [x^i] P_{N-1} \cdot [x^j] g_N = \sum_{m \ge 0,\ Nm \le n} [x^{n - Nm}] P_{N-1}$.
9. By the induction hypothesis this is $\sum_{m \ge 0,\ Nm \le n} c_{N-1}(n - Nm)$. Sorting the tuples of length $N$ by their last entry $m_N = m$ shows that this sum is $c_N(n)$.
10. A partition of $n$ with all parts at most $N$ is determined by the numbers $m_k$ of its parts equal to $k$, for $1 \le k \le N$. These satisfy $\sum_k k\, m_k = n$, and each such tuple gives one partition.
11. So $c_N(n)$ is the number of partitions of $n$ with all parts at most $N$.
12. Let $N \ge n$. Each part of a partition of $n$ is at most $n \le N$. So $c_N(n)$ is the number of all partitions of $n$, which is the partition function value $p(n)$.
13. By steps 6 and 12, $[x^n] P_N = p(n)$ for every $N \ge n$. So the coefficients in step 4 do not depend on $N$, and the infinite product is well defined.
14. Two series with the same coefficients are equal, by the definition of the coefficients. Hence $\prod_{k \ge 1} \frac{1}{1 - x^k} = \sum_{n \ge 0} p(n)\, x^n$, the generating function of $p$.