IMC 2012 · Day 1 · P1

The statement is true for $n = 1$, because $p(0) = p(1) = 1$ and the only partition of 1 contains the term 1. In the rest of the solution we assume $n \ge 2$.

Let $P_n = \{ (a_1, \dots, a_k) : k \in \mathbb{N},\ a_1 \ge \dots \ge a_k,\ a_1 + \dots + a_k = n \}$ be the set of partitions of $n$, and let $Q_n = \{ (a_1, \dots, a_k) \in P_n : a_k = 1 \}$ the set of those partitions of $n$ that contain the term 1. The set of those partitions of $n$ that do not contain 1 as a term, is $P_n \setminus Q_n$. We have to prove that $|P_n \setminus Q_n| = |P_n| - |P_{n-1}|$.

Define the map $\varphi : P_{n-1} \to Q_n$ as $$\varphi(a_1, \dots, a_k) = (a_1, \dots, a_k, 1).$$ This is a partition of $n$ containing 1 as a term (so indeed $\varphi(a_1, \dots, a_k) \in Q_n$). Moreover, each partition $(a_1, \dots, a_k, 1) \in Q_n$ uniquely determines $(a_1, \dots, a_k)$. Therefore the map $\varphi$ is a bijection between the sets $P_{n-1}$ and $Q_n$. Then $|P_{n-1}| = |Q_n|$. Since $Q_n \subset P_n$, $$|P_n \setminus Q_n| = |P_n| - |Q_n| = |P_n| - |P_{n-1}| = p(n) - p(n-1).$$

(outline) Denote by $q(n)$ the number of partitions of $n$ not containing 1 as term ($q(0) = 1$ as the only partition of 0 is the empty sum), and define the generating functions $$F(x) = \sum_{n=0}^{\infty} p(n) x^n \quad \text{and} \quad G(x) = \sum_{n=0}^{\infty} q(n) x^n.$$ Since $q(n) \le p(n) < 2^n$, these series converge in some interval, say for $|x| < \frac{1}{2}$, and the values uniquely determine the coefficients.

According to Euler's argument, we have $$F(x) = \sum_{n=0}^{\infty} p(n) x^n = \prod_{k=1}^{\infty} (1 + x^k + x^{2k} + \dots) = \prod_{k=1}^{\infty} \frac{1}{1 - x^k}$$ and $$G(x) = \sum_{n=0}^{\infty} q(n) x^n = \prod_{k=2}^{\infty} (1 + x^k + x^{2k} + \dots) = \prod_{k=2}^{\infty} \frac{1}{1 - x^k}.$$ Then $G(x) = (1 - x) F(x)$. Comparing the coefficient of $x^n$ in this identity we get $q(n) = p(n) - p(n-1)$.