Prove combinatorially the recurrence $p_n(k) = p_n(k−n) + p_{n−1}(k−1)$ for all $0<n≤k$.

Question

Recall that $p_n(k)$ counts the number of partitions of $k$ into exactly $n$ positive parts (or, alternatively, into any number of parts the largest of which has size $n$).

Answer 1

Hints for decomposing the collection of partitions into two groups:

---

Using the first interpretation: Given a partition of $k$ into exactly $n$ positive parts, there are two cases.

• Case 1: Each part has size $\ge 2$.
• Case 2: There is at least one part of size $1$.

---

Using the second interpretation: Given a partition of $k$ into positive parts, the largest of which has size $n$, there are two cases.

• Case 1: There at least two parts of size $n$.
• Case 2: There is exactly one part of size $n$.