# Prove combinatorially the recurrence p n </msub> ( k ) = p n </ms

Prove combinatorially the recurrence ${p}_{n}\left(k\right)={p}_{n}\left(k-n\right)+{p}_{n-1}\left(k-1\right)$ for all $0
Recall that ${p}_{n}\left(k\right)$ counts the number of partitions of k into exactly n positive parts (or, alternatively, into any number of parts the largest of which has size n).
You can still ask an expert for help

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

fongama33
Step 1
Hints for decomposing the collection of partitions into two groups:
Using the first interpretation: Given a partition of k into exactly n positive parts, there are two cases.
Case 1: Each part has size $\ge 2$.
Case 2: There is at least one part of size 1.
Step 2
Using the second interpretation: Given a partition of k into positive parts, the largest of which has size n, there are two cases.
Case 1: There at least two parts of size n.
Case 2: There is exactly one part of size n.