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: A partition of $n$ into $k$ parts can either have a $1$, or have no $1$'s.
