# Elementary proof of a bound on the order of the partition function

I am interested in the asymptotic order of the partition function $p(n)$.

The paper Asymptotic Formulae in Combinatory Analysis proves there are constants $A$,$B$ such that $e^{A\sqrt{n}} < p(n) < e^{B\sqrt{n}}$ by elementary means. Here is the argument for one side of the inequality, it is just the inductive step which I have not understood:

I assume that $p_r(n)$ is defined to be $0$ for negative $n$, then the inequalty (2.22) does not hold for these $n$. In which case the sum $\{n^{s-1} + (n-s-1)^{s-1} + (n-2s-2)^{s-1} + \ldots\}$ must be finite, ending before $n-ks-k$ becomes negative. On the other hand the use of telescoping down to $n^s$ suggests that the sum is infinite, otherwise we would end up with $n^s - (n-ks-k)^{s-1}$ and are unable to throw away the $k$ term.

Thank you to anyone who will help me understand this argument.

-

Write $n = Q(s-1)+R$ with $0 \le R < s-1$. The final term in the first line of the induction step (i.e. the three-line display equation) is $R^{s-1}$. As you have noted, as written the author seems to imply that the final term in the next line of the inequality should be $(R^s - (R-(s-1))^s)/s(s+1)$. But in fact $R^s/s(s+1)$ will do, because $R^{s-1} \ge R^s/s(s+1)$ (recall that $R < s-1$), and then your sum telescopes just fine.