18
$\begingroup$

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.
More information about the partition numbers can be found at OEIS.
Any help would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ See partition function formulas. $\endgroup$ – Lucian Jul 12 '15 at 0:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Winther Jul 12 '15 at 1:06
  • $\begingroup$ My poor English made me misunderstand the comment of Winther. I deleted the wrong solution had given. $\endgroup$ – Piquito Jul 23 '15 at 12:33
  • 1
    $\begingroup$ 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... $\endgroup$ – Noam D. Elkies Jul 29 '15 at 15:56
  • $\begingroup$ It's Turkey IMO team selection test, year 2003. $\endgroup$ – TBTD Apr 24 '17 at 4:26
9
+50
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Scientifica Jul 29 '15 at 11:24
  • 1
    $\begingroup$ 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}$. $\endgroup$ – David E Speyer Jul 29 '15 at 12:50
  • $\begingroup$ 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. $\endgroup$ – Noam D. Elkies Jul 29 '15 at 15:01
  • $\begingroup$ Fixed too soon before noticing another such typo: Lemma 3, sum of $a_i$, not of $a_m$. Will fix in the next round. $\endgroup$ – Noam D. Elkies Jul 29 '15 at 15:52
  • $\begingroup$ ... and "conversely" the sums over $i$ in Lemma 5 should be over $m$ ... $\endgroup$ – Noam D. Elkies Jul 29 '15 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.