In: Advanced Math
Prove that for all integers n ≥ 2, the number p(n) − p(n − 1) is equal
to the number of partitions of n in which the two largest parts are
equal.
Answer :-
Let be construct a bijection from the set of all partitions of n−1 onto the set of all partitions of n that have at least one part equal to one. The bijection is just simply adding a part equal to 1 to the end of each partition of n−1.
If the partition has its two largest sets with equal size send that partition to the following partition: order the two largest sets depending on the minimimum element and send the partition P to the partition which is equal to P in every sense except for the fact that the n belongs to the set that was one of the largest sets in P and had the minimum element among those sets.
If the partition has its two largest sets with size P then send the partition of n that is identical to P only nn belongs to a singleton set.
This function is clearly injective because given a partition of n we can easily recover from which partition of size n−1 it came (and it is unique)
On the other hand it is not surjective, this is because if a partition of n comes from a partition of n−1 and satisfies that its largest set has the element n then there is always a set that has exactly 1 element less than the largest set. While there are many partitions of n in which the largest two sets have different sizes which satisfy that the largest set contains n, but the second smallest set does not have 1 element less than the largest set.
In conclusion we gave a function from the set of partitions of n−1 to the set of partitions of n in which the two largest sets have different sizes that it injective but no surjective, this tells us there are strictly less partitions of n−1 than partitions of nn in which the two largest sets have different sizes.