Let p(n) denote the number of partitions of n, the number of different ways to write n as a sum of positive integers. for example:

p(5) = 7 since 5 = 1+1+1+1+1 = 2+1+1+1 = 2+2+1 = 3+1+1 = 3+2 = 4+1

similarly, it can be shown that p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, etc. (the prime numbers)

Using a proof by induction, show that p(n) is prime for all n.

Question

Let p(n) denote the number of partitions of n, the number of different ways to write n as a sum of positive integers. for example:

p(5) = 7 since 5 = 1+1+1+1+1 = 2+1+1+1 = 2+2+1 = 3+1+1 = 3+2 = 4+1

similarly, it can be shown that p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, etc. (the prime numbers)

Using a proof by induction, show that p(n) is prime for all n.

anonymous · Answer

well, I think I made a big mistake there: p(1) is not prime

anonymous · Answer

so my proof of induction won't work here :(

anonymous · Answer

you are right

anonymous · Answer

but wait! can't we prove by induction that p(2), p(3), ..., p(n) (excluding 1) runs through the prime numbers?