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.
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.
