Partitions of $n$: proving $p(n+2)+ p(n) \geq 2p(n+1)$

1.7k Views Asked by At

For $n \geq 2$ give an alternative description of $p(n) - p(n-1)$ as the number of partitions of $n$ which have a certain property.

I have done that part, it is fine. I have not included it here as I am not accustomed with LaTeX but can put it up if wanted. But then it says

Hence or otherwise prove $p(n+2)+ p(n) \geq 2p(n+1)$.

This is the part I do not know how to do. Any help appreciated thank you

2

There are 2 best solutions below

10
On BEST ANSWER

Hint: The stated inequality is equivalent to $$p(n+2)-p(n+1)\ge p(n+1)-p(n)$$

2
On

The difference $p(n)-p(n-1)$ is the number of partitions of $n$ that do not contain 1/with smallest part (wsp) 2 -- also denoted $p(2,n)$, where $p(\cdot,\cdot)$ is the intermediate function. Using Sharkos's hint, we understand that we aim to prove that $p(2,n)$ is increasing. One way to prove this is to find an injection that, to any partition of $n$ wsp 2, assigns a partition of $n+1$ wsp 2.

Clearly, by adding 1 to any such partition of $n$, we obtain a partition of $n+1$. But doing so by simply adding "+1" to the sum would not make it a valid partition of $n+1$ wsp 2 (the smallest part would be 1).

Instead, consider adding 1 to any of the existing addends of any given partition $P$ of $n$ wsp 2. Our goal is to ensure that we would not obtain the same partition of $n+1$ twice (since it wouldn't be an injection then), and this can be achieved by chosing to systematically add 1 to the greatest element of $P$.

Doing so, we obtain the desired injection, and therefore we prove that there are at least as many partitions of $n+1$ than of $n$ wsp 2.