(Proposed by Fedor Duzhin, Nanyang Technological University)
Solution 1. 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≥2.
Let Pn={(a1,…,ak):k∈N, a1≥…≥ak, a1+…+ak=n} be the set of partitions of n, and let Qn={(a1,…,ak)∈Pn:ak=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 Pn∖Qn. We have to prove that ∣Pn∖Qn∣=∣Pn∣−∣Pn−1∣.
Define the map φ:Pn−1→Qn as
φ(a1,…,ak)=(a1,…,ak,1).
This is a partition of
n containing 1 as a term (so indeed
φ(a1,…,ak)∈Qn). Moreover, each partition
(a1,…,ak,1)∈Qn uniquely determines
(a1,…,ak). Therefore the map
φ is a bijection between the sets
Pn−1 and
Qn. Then
∣Pn−1∣=∣Qn∣. Since
Qn⊂Pn,
∣Pn∖Qn∣=∣Pn∣−∣Qn∣=∣Pn∣−∣Pn−1∣=p(n)−p(n−1).
Solution 2 (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)=n=0∑∞p(n)xnandG(x)=n=0∑∞q(n)xn.
Since
q(n)≤p(n)<2n, these series converge in some interval, say for
∣x∣<21, and the values uniquely determine the coefficients.
According to Euler's argument, we have
F(x)=n=0∑∞p(n)xn=k=1∏∞(1+xk+x2k+…)=k=1∏∞1−xk1
and
G(x)=n=0∑∞q(n)xn=k=2∏∞(1+xk+x2k+…)=k=2∏∞1−xk1.
Then
G(x)=(1−x)F(x). Comparing the coefficient of
xn in this identity we get
q(n)=p(n)−p(n−1).
Transcribed from the official solutions, page 1. This transcription has not been checked a second time; if in doubt, look at the original.