lower bounds for growth of a sequence Suppose I have an (integer valued, but it probably does not matter) monotonically increasing function $f: \mathbb{N} \to \mathbb{R},$ which satisfies 
$$\sum_{i=1}^n f(i) < f(2 n).$$ What can we say about the speed of growth of this function?
 A: This is an extended remark. It is easy to see that there is a minorant $g(n)$ of
all such increasing sequences with fixed $f(1)$: put $g(1)=f(1)$,
$$g(2^{n+1})=\sum_{1}^n g(k),$$
and $g(k)=g(2^n)$ for $2^n<k<2^{n+1}$. These conditions define $g$ uniquely,
and we have $f(k)\geq g(k)$ for all $k$. The equation for $g$ suggests that we consider the continuous analog:
$$F(2x)=\int_0^xF(t)dt, \quad\mbox{or}\quad F'(x)=(1/2)F(x/2).$$
Adding the initial condition $F(0)=1$ we obtain the unique entire solution
$$F(x)=\sum_{n=0}^\infty 2^{-n(n+1)/2}\frac{z^n}{n!},$$
the famous entire function which Alan Sokal calls the "deformed exponential". The growth rate of this $F$ is easy to find with the standard
methods of the theory of entire functions: it is $\log F(x)\sim \exp (c\log^2x)$, where
$c=1/(2\log 2)$. (The growth of $F$ is like the maximal term in its Taylor series. In our case this maximal term dominates the whole sum).
Ref. A. Sokal, Some wonderful conjectures...  http://www.maths.qmul.ac.uk/~pjc/csgnotes/sokal/
A: Here is the trivial part where I'm pretty sure that the way is close to the most elegant requested:
$f(n)=e^{c\log^2 n}$ with $c=\frac 1{2\log 2}$ satisfies the inequality.
Indeed, 
$$
f(2n)=e^{c\log^2 n+2c\log 2\log n+c\log^22}\ge f(n)n\ge \sum_{i=1}^nf(i)
$$
Here is the crude lower bound $f(n)\ge \delta f(1)e^{c\log^2 n}$ with any $c<\frac 1{2\log 2}$ and $\delta=\delta(c)>0$.
For any finite number of terms the estimate holds if we choose $\delta>0$ small enough. Suppose that we have the estimate up to $2n-1$ with sufficiently large $n$. Then
$$
f(2n)\ge \delta\sum_{0\le j<\varepsilon n}e^{c\log^2(n-j)}\ge\varepsilon ne^{c\log^2 n+2c\log(1-\varepsilon)\log n}
\\
=e^{c\log^2 n+\log n(1+2c\log(1-\varepsilon))+\log\varepsilon}\ge e^{c\log^2(2n+1)}
$$
provided that $c<\frac 1{2\log 2}$, $\varepsilon<\varepsilon(c)$, and $n\ge N(c,\varepsilon)$,
so we are fine up to $2n+1$.
I wouldn't call this "elegant" and it is way too crude (we can actually get an asymptotic behavior; then there will be a correction logarithmic term in the exponent, etc.), but I'll leave it here for now.
Elementary upper bound for $p(n)$.
First, choose how many different numbers you want in your partition (can choose any $k\le \sqrt{2n}$, so $\sqrt{2n}$ choices here.
Next choose the actual numbers you want to use. They should sum up to $\le n$, so choose $k$ points between $1$ and $n$ and view your numbers as the differences between successive points (including 0); if two of those coincide, discard the configuration, otherwise note that each set appeared $k!$ times, so we have ${n\choose k}/k!\le \frac{n^k}{(k!)^2}$ options here.
Now, choose the multiplicities so that the sum is $\le n$. Obviously, the worst case scenario is when you have $1,2,\dots,k$. If your students don't mind elementary geometry, just associate with each integer solution of $a_1+2a_2+\dots+ka_k$ a parallelepiped in $\mathbb R^k$ of size $1\times 2\times\dots\times k$ with the corner at $(a_1,2a_2,\dots, ka_k)$. Since $1+2+\dots +k\le n$, they are all contained in the simplex $x_1+\dots+x_k\le 2n$, $x_j\ge 0$, so the volumetric bound gives $\frac{(2n)^k}{(k!)^2}$.
Now all we need to show is that $\frac{n^k}{(k!)^2}=\left[\frac{(\sqrt n)^k}{k!}\right]^2\le e^{2\sqrt n}$.
If your students are afraid of $k$-dimensional geometry or ignorant of the series expansion of $e^x$, let me know and I'll try to circumvent both :-)
