Show that $p(n,k)=p(n-1, k-1)+p^2(n, k)$, Partition Theory

Question

I'm struggling to prove this as I'm not sure how to do so with words/equations as opposed to visually. $p^2(n,k)$ denotes the number of partitions of n having exactly k parts with each part greater than or equal to 2

Answer 1

Consider two cases for the partitions counted by $p(n,k)$:

1. the partition has at least one 1, or

2. each part of the partition is 2 or more.

The type 2 partitions are exactly counted by your $p^2(n,k)$ (although the notation makes me shudder). To show that $p(n-1,k-1)$ counts the type 1 partitions, use the following bijection.

• Given a type 1 partition, delete the last 1 (we are guaranteed there is at least one 1). This leaves a partition of $n-1$ with $k-1$ parts.
• Given a partition counted by $p(n-1,k-1)$, add a $k$th part 1 at the end* to produce a $k$ part partition of $n$ which, by construction, has at least one 1.

*One has to be careful about adding parts to a partition, e.g., putting a 2 at the end of (3, 1) would not work. But adding a 1 is always OK.