Question

In: Advanced Math

Prove that for all integers n ≥ 2, the number p(n) − p(n − 1) is...

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.

Solutions

Expert Solution

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.


Related Solutions

prove 2 is a factor of (n+1)(n+2) for all positive integers
prove 2 is a factor of (n+1)(n+2) for all positive integers
Prove these scenarios by mathematical induction: (1) Prove n2 < 2n for all integers n>4 (2)...
Prove these scenarios by mathematical induction: (1) Prove n2 < 2n for all integers n>4 (2) Prove that a finite set with n elements has 2n subsets (3) Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps
For all integers n > 2, show that the number of integer partitions of n in...
For all integers n > 2, show that the number of integer partitions of n in which each part is greater than one is given by p(n)-p(n-1), where p(n) is the number of integer partitions of n.
Prove via induction the following properties of Pascal’s Triangle: •P(n,2)=(n(n-1))/2 • P(n+m+1,n) = P(n+m,n)+P(n+m−1,n−1)+P(n+m−2,n−2)+···+P(m,0) for all...
Prove via induction the following properties of Pascal’s Triangle: •P(n,2)=(n(n-1))/2 • P(n+m+1,n) = P(n+m,n)+P(n+m−1,n−1)+P(n+m−2,n−2)+···+P(m,0) for all m ≥ 0
Prove that the following is true for all positive integers n: n is odd if and...
Prove that the following is true for all positive integers n: n is odd if and only if n2 is odd.
Use induction to prove that 8^n - 3^n is divisible by 5 for all integers n>=1.
Use induction to prove that 8^n - 3^n is divisible by 5 for all integers n>=1.
Use double induction to prove that (m+ 1)^n> mn for all positive integers m; n
Use double induction to prove that (m+ 1)^n> mn for all positive integers m; n
Let x, y be integers, and n be a natural number. Prove that x ^(2n) −...
Let x, y be integers, and n be a natural number. Prove that x ^(2n) − y ^(2n) is divisible by x + y
Prove that the number of partitions of n into parts of size 1 and 2 is...
Prove that the number of partitions of n into parts of size 1 and 2 is equal to the number of partitions of n + 3 into exactly two distinct parts
Prove that if the integers 1, 2, 3, . . . , 65 are arranged in...
Prove that if the integers 1, 2, 3, . . . , 65 are arranged in any order, then it is possible to look either left to right or right to left through the list and find nine numbers that are in increasing order
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT