Problem 1396

1. Define the partition function and generating functions:
Let $p(n)$ be the number of ways to express $n$ as a sum of natural numbers, where the order of summands does not matter. The generating function for $p(n)$ is given by:
$$\sum_{n \geq 0} p(n) x^n = \prod_{n \geq 1} \frac{1}{1 - x^n}$$

2. Express the generating function for partitions into distinct parts:
Let $D(n)$ be the number of ways to express $n$ as a sum of distinct positive integers. The generating function for $D(n)$ is:
$$\sum_{n \geq 0} D(n) x^n = \prod_{n \geq 1} (1 + x^n)$$
Using the identity for the product of sums:
$$\prod_{n \geq 1} (1 + x^n) = \prod_{n \geq 1} \frac{1 - x^{2n}}{1 - x^n}$$

3. Express the generating function for partitions into odd parts:
Let $O(n)$ be the number of ways to express $n$ as a sum of odd positive integers. The generating function for $O(n)$ is:
$$\sum_{n \geq 0} O(n) x^n = \prod_{n \geq 0} \frac{1}{1 - x^{2n+1}}$$

4. Equate the generating functions:
By the Pentagonal Number Theorem, we have:
$$\prod_{n \geq 1} (1 - x^n) = \sum_{n \in \mathbb{Z}} (-1)^n x^{(3n^2 + n)/2}$$
This identity helps in understanding the parity of $p(n)$.

5. Kolberg's result:
Kolberg's result states that for an infinite number of $n$, $p(n)$ is even, and for an infinite number of $n$, $p(n)$ is odd. This is based on the identities:
$$\sum_{n \geq 0} p(n) x^n = \prod_{n \ge 1} \frac{1}{1 - x^n}$$
and
$$\prod_{n \ge 1} (1 - x^n) = \sum_{n \in \mathbb{Z}} (-1)^n x^{(3n^2 + n)/2}$$

6. Conclusion:
The parity of $p(n)$ is a complex problem, but Kolberg's proof shows that there are infinitely many $n$ for which $p(n)$ is even and infinitely many $n$ for which $p(n)$ is odd.

$\blacksquare$