# Proving an Inequality Involving Integer Partitions

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.

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$

• That was an excellent answer! I'm familiar with Young diagrams (via Ferrers diagrams), but I'm glad you provided proofs both with and without them. Thank you very much! Sep 27, 2013 at 7:27