Let p(n) be the number of partitions of the natural number n into natural summands. The diversity of a partition is by definition the number of different summands in it. Denote by q(n) the sum of the diversities of all the p(n) partitions of n.
(For example, p(4)=5, the five distinct partitions of 4 being 4,3+1,2+2,2+1+1,1+1+1+1, and g(4)=1+2+1+2+1=7.)
Prove that, for all natural numbers n,
(a) q(n)=1+P(1)+P(2)+p(3)+...+p(n−1),
(b) q(n)<2np(n). (AV Zelevinskiy, Moscow) partitionnumber theorycombinatorics