Number partition – prove recursive formula

Prove the following recursive formula:

$$ p_{k} (n) = p_{k-1} (n-1) + p_{k} (n-k)$$

Would you give me any hints how to start with this?

Edit: I’m sorry:

$p_{k} (n)$ – it is a number of partitions $n$ into $k$ parts.


$p_{2} (4) = 2$ because $4= 3+1$ and $4=2+2$

Solutions Collecting From Web of "Number partition – prove recursive formula"

HINT: $p_k(n)$ is the number of partitions of $n$ into $k$ parts. There are two kinds of partitions of $n$ into $k$ parts: those having at least one part of size $1$, and those in which every part has size at least $2$. If every part has size at least $2$, you can subtract one from each part to get a partition of $n-k$ into $k$ parts. And if there’s a part of size $1$, you can … ?

Hint: A partition of $n$ into $k$ parts can either have a $1$, or have no $1$’s.