Let $|n,k|$ denote the number of partitions of $n$ into $k$ distinct parts. Prove
$$|n,k| = |n-k,k-1| + |n-k,k|$$
Workings:
LHS counts the number of partitions of $n$ into $k$ distinct parts.
RHS:
Break this into two cases
I: $1$ is the smallest part
II: The smallest part is $>1$
I: This can be counted $|n-k,k-1|$ ways.
II: This can be counted $|n-k,k|$ ways.
Summing these together gives the RHS.
Edit: Is my proof correct?
A simpler way to state the same is the following:
Suppose $A = \{a_0, …, a_{k-1} \}$ is a partition of $n$ into $k$ positive distinct integers. Then take the following partition: $$ A' = \{a_0-1, …, a_{k-1}-1\} $$ so $$ \sum A' = n-k $$ and $A'$ has either $k$ or $k-1$ distinct positive integers (at most one of them is $0$).
This process defines a function $f: P(n,k) \to P(n-k, k) \cup P(n-k, k-1)$.
On the other side, every partition $B \in P(n-k, k)$ can be transformed in a partition $B' \in P(n,k)$ by adding $1$ to each integer, and every partition $C \in P(n-k, k-1)$ can be taken to $C' \in P(n,k)$ by ading $1$ to each integer, and finally adding the integer $1$ itself.
It's now easy to show that these two functions are inverse one of the other, so they are bijections.