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