Let $p_{k}(n)$ indicate the number of partitions of n into k parts. Prove: $$p_{k}(n) = p_{k-1}(n-1) + p_{k}(n-k)$$
Example: There are two partitions of $5$ into three parts.
$5 = 3+1+1$
$5 = 2+2+1$
My approach was going to start out by proving by induction. But quickly, I don't even seem to understand what this recursion is talking about. Is it possible to even do it by induction? Any help would be great. I've proved a couple of recursion problems by induction like the Fibonacci ones but I can't wrap my head around this one.
You don't need induction.
Let $A_k(n)$ be the number of partitions of $n$ into $k$ parts where (at least) one of the parts is $1$, and let $B_k(n)$ be the number of partitions of $n$ into $k$ parts all of which are greater than $1$.
Then it is clear that $p_k(n) = A_k(n) + B_k(n)$, and it is also easy to see that $A_k(n) = p_{k-1}(n-1)$ and $B_k(n) = p_k(n-k)$.