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
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
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 if p is a polynomial with degree n and k is a real number...
Prove that if p is a polynomial with degree n and k is a real number so that p(k) = 0, then p(x)=(x-k)q(x) where q is a polynomial of degree n-1. Must use the fact that a^n-b^n=(a-b)(a^(n-1) + a^(n-2)*b + ... + ab^(n-2) + b^(n-1)).
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT