# On the inequality $\frac{1+p(1)+p(2) + \dots + p(n-1)}{p(n)} \leq \sqrt {2n}.$

For all positive integers $n$, $p(n)$ is the number of partitions of $n$ as the sum of positive integers (the partition numbers); e.g. $p(4)=5$ since $4=1+1+1+1=1+1+2=1+3=2+2=4.$

Prove that: $\dfrac{1+p(1)+p(2) + \dots + p(n-1)}{p(n)} \leq \sqrt {2n}.$

This problem is from a Turkish contest. Maybe it's a well known result.
Any help would be appreciated.

• – Lucian Jul 12 '15 at 0:14
• The result follows by induction given if you can prove $\frac{p(n+1)}{p(n)} \geq \frac{\sqrt{2n}+1}{\sqrt{2n+2}}$. This result does follow from the Hardy–Ramanujan asymptotical approximation for $p(n)$ (for large $n$), however this is highly overkill for a contest problem and not a very elegant solution imo so I'm sure there must be a simpler more elementary way of proving this. – Winther Jul 12 '15 at 1:06
• My poor English made me misunderstand the comment of Winther. I deleted the wrong solution had given. – Piquito Jul 23 '15 at 12:33
• By Hardy-Ramanujan the ratio is asymptotic to $\sqrt{6n}\,/\,\pi$, so $\sqrt{2n}$ is too large but only by a constant factor $\pi / \sqrt{3} = 1.8138\!-$. So a proof cannot be too generous with intermediate inequalities... – Noam D. Elkies Jul 29 '15 at 15:56
• It's Turkey IMO team selection test, year 2003. – TBTD Apr 24 '17 at 4:26

We give a proof of the strict inequality $$\frac{1 + p(1) + p(2) + \cdots + p(n-1)}{p(n)} < \sqrt{2n}.$$ The square root arises by first proving an upper bound $(k-1)/2 + (n/k)$ for any integer $k \geq 1$, and then minimizing over $k$; this kind of thing is seen often in analysis, but isn't a common tactic in the inequalities that appear in competition math.

It is convenient and natural to extend the definition of $p(n)$ to all integers by setting $p(n) = 0$ for all $n < 0$ and $p(0) = 1$. In particular, the numerator $1 + p(1) + p(2) + p(3) + \cdots$ in the fraction of interest is $$s_1 := \sum_{n' < n} p(n') = \sum_{m=1}^\infty p(n-m).$$ Then for all $n$ the $p(n)$ partitions of $n$ can be identified with solutions of $$n = \sum_{i=1}^\infty i a_i = a_1 + 2 a_2 + 3 a_3 + 4 a_4 + \cdots$$ in nonnegative integers $a_i$ that vanish for all but finitely many $i$. (Each $a_i$ is the number of times that $i$ occurs in the partition.) Of course $p(n)$ is the sum of $1$ over such solutions $(a_1,a_2,a_3,\ldots)$. The first key point is:

Lemma 1. $s_1$ is the sum of $a_1$ over partitions $(a_1,a_2,a_3,\ldots)$ of $n$.

This can be proved using generating functions, or combinatorially from

Lemma 2. $p(n) - p(n-1)$ is the number of partitions $(a_1,a_2,a_3,\ldots)$ of $n$ with $a_1 = 0$.

Proof: The partitions with $a_1 > 0$ are in bijection with the partitions of $n-1$ by $(a_1,a_2,a_3,\ldots) \mapsto (a_1-1,a_2,a_3,\ldots)$. $\Box$

(Corollary 1: $p(n) \geq p(n-1)$ for all $n$, with equality iff $n=1$.)

Now Lemma 1 can be proved by bijecting, for each $m$, the partitions of $n$ with $a_1 = m$ with partitions of $n-m$ with $a_1=0$, and summing over $m$.

The next point is to generalize Lemma 1 to a formula for the sum of $a_i$ over partitions of $n$:

Lemma 3. For $i \geq 1$ define $$s_i := \sum_{m=1}^\infty p(n-im).$$ Then $s_i$ is the sum of $a_m$ over partitions $(a_1,a_2,a_3,\ldots)$ of $n$.

Proof as before, generalizing Lemma 2 to: $p(n) - p(n-i)$ is the number of partitions $(a_1,a_2,a_3,\ldots)$ of $n$ with $a_i = 0$. $\Box$

Lemma 4. $\sum_{i\geq 1} i s_i = n p(n)$.

Proof: By Lemma 3 $\sum_{i\geq 1} i s_i$ is the sum, again over partitions of $n$, of $\sum_i i a_i$, which is $n$. $\Box$

[David Speyer notes in a comment that this too can be obtained from the generating function $\sum_{n\geq 0} p(n) x^n = \prod_{i \geq 1} (1-x^i)^{-1}$, here by applying the operator $x \frac{d}{dx}$.]

Corollary 2. For any $k$ we have $\sum_{i=1}^k i s_i \leq n p(n)$.

That's an inequality on a linear combination of $s_1,\ldots,s_k$. To reach an inequality on just $s_1$, we use:

Lemma 5. For all $i\geq 1$ we have $s_1 + p(n) \leq i(s_i + p(n))$.

Proof: Note that $s_i + p(n) = \sum_{i \geq 0} p(n-im)$. Hence

$i (s_i + p(n)) = \sum_{i \geq 0} i p(n-im)$

$\phantom{i (s_i + p(n))} \leq \sum_{i \geq 0} \bigl(p(n-im) + p(n-im-1) + p(n-im-2) + \cdots + p(n-im-(i-1) \bigr)$

$\phantom{i (s_i + p(n))} = s_1 + p(n),$

using Corollary 1 in the middle step. $\Box$

Combining Lemma 5 with Corollary 2 yields $$np(n) \geq \sum_{i=1}^k i s_i \geq \sum_{i=1}^k (s_1 - (i-1) p_n) = k s_1 - {k \choose 2} p(n),$$ whence $$s_1 \leq \left( \frac{k-1}{2} + \frac{n}{k} \right) p(n).$$ It remains to choose the integer $k$ so as to minimize the upper bound $(k-1)/2 + (n/k)$. The final lemma is elementary but takes some verbiage to prove in full, and this post is already quite long, so I'll leave it as an exercise:

Lemma 6: The minimal value of $\frac{k-1}{2} + \frac{n}{k}$ over integers $k \geq 1$ is attained iff ${k \choose 2} \leq n \leq {k+1 \choose 2}$. This minimal value is smaller than $\sqrt{2n}$ for all $n$.

(Note that if $n = {\kappa \choose 2}$ then there are two choices of $k$, namely $k=\kappa$ and $k = \kappa-1$; else the choice is unique. For large $n$, the optimal value(s) of $k$ grow(s) as $\sqrt{n/2}$, which is indeed where $k/2 + n/k$ attains its minimum of $\sqrt{2n}$.)

Combining Lemmas 6 with the inequality for $s_1$ (displayed below Lemma 5) yields the desired inequality $s_1 / p(n) < \sqrt{2n}$, QED.

• In the second line I believe it should be $p(n)=0$ for all $n<0$ instead of $p(0)=0$ for all $n<0$. – Scientifica Jul 29 '15 at 11:24
• Wow. One observation which makes things more obvious to me: Lemma $4$ is the result of hitting the equation $\prod (1-x^k)^{-1} = \sum p(n) x^n$ with $x \frac{d}{dx}$. – David E Speyer Jul 29 '15 at 12:50
• Scientifica: thanks, I'll fix this. David Speyer: I started out trying to use this identity but couldn't see where to go with it until it came up again via the $s_i$. I can still add the $x \, d/dx$ interpretation. – Noam D. Elkies Jul 29 '15 at 15:01
• Fixed too soon before noticing another such typo: Lemma 3, sum of $a_i$, not of $a_m$. Will fix in the next round. – Noam D. Elkies Jul 29 '15 at 15:52
• ... and "conversely" the sums over $i$ in Lemma 5 should be over $m$ ... – Noam D. Elkies Jul 29 '15 at 16:16