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. 
Example 
$p_{2} (4) = 2$  because $4= 3+1$ and $4=2+2$

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 ... ?
