Proving an Inequality Involving Integer Partitions

Question

I am having a bit of trouble beginning the following:

Prove that for all positive integers $n$, the inequality $p(n)^2<p(n^2+2n)$ holds, where $p(n)$ is defined as the number of all partitions of $n$.

I initially considered weak induction on n, but am not sure if that is the correct way to begin. Is there an alternate, stronger path (such as a combinatorial proof) I should consider? I feel like I'm making this more difficult than it should be, and I apologize if this is the case.

Thank you in advance!

Answer 1

If you know what a Young diagram is and how it relates to partitions, here's a neat argument:

Take a $n$ by $n$ box and put a Young diagram partitioning n on the right side, and one underneath it. What do you get? a Young diagram partitioning $n^2 + 2n$. What if you take the box away? You get a pair of Young diagrams each partitioning $n$. This gives an injection of pairs of $n$ partitions into partitions of $n^2 + 2n$

If you don't know about Young diagrams ( you should learn them! They're really interesting, fun, and important ), the same argument can be made less geometrically. Take any two partitions of $n$ and add $n + n + n + \ldots + n$ ( $n$ added $n$ times ) to the first partition. What you get is a partition of $n^2 + n$ with parts all greater than or equal to $n$, so you just add your other partition of $n$ to that, and you get a partition of $n^2 + 2n$. It's not too hard to see this algorithm is injective.

Example where $n = 6$ $$ f = 3 + 2 + 1 $$ $$ g = 3 + 3 $$ $$ h = 9 + 8 + 7 + 6 + 6 + 6 + 3 + 3 $$

So $f$ and $g$ are partitions of $n$ and $h$ is a partition of $n^2 + 2n$ formed in the way described above.

Really the Young diagram version is cuter though!

Oh, to get strict inequality, just take the partition which is all ones of $n^2 + 2n$