Approximation of the number of partitions of n, denoted p(n)

Question

I managed to prove that $p(n)\ge \max_{1\le k\le n}{{n-1\choose k-1}\over k!}$,that wasn't hard. Now I need to use this result to prove that there exists a constant c>0 for which $p(n)\ge e^{c\sqrt n}$ for any $n\in \mathbb{N}$. I tried to use Stirling's approximation here, but didn't get the result I want. Any hints?

Answer 1

First find for which $k$ the expression

$$a(n,k) = \frac{1}{k!}\binom{n-1}{k-1} = \frac{(n-1)!}{k!(k-1)!(n-k)!}$$

reaches its maximum. Since $a(n,k) > 0$ for $1 \leqslant k \leqslant n$ and

$$\frac{a(n,k+1)}{a(n,k)} = \frac{n-k}{(k+1)k}$$

we see that

$$a(n,k+1) < a(n,k) \iff n - k < (k+1)k \iff n+1 < (k+1)^2,$$

so the maximum is attained for $k = \lfloor \sqrt{n+1}\rfloor$.

Now recall Stirling's approximation

$$\log m! = \bigl(m + \tfrac{1}{2}\bigr)\log m - m + \log \sqrt{2\pi} + O\biggl(\frac{1}{m}\biggr)$$

and the equivalent

$$\log (m-1)! = \bigl(m - \tfrac{1}{2}\bigr)\log m - m + \log \sqrt{2\pi} + O\biggl(\frac{1}{m}\biggr)\,.$$

Plugging these into

$$\log p(n) \geqslant \log (n-1)! - \log (n-k)! - \log (k-1)! - \log k!$$

yields

\begin{align} \log p(n) &\geqslant \bigl(n - \tfrac{1}{2}\bigr) \log n - n + \log \sqrt{2\pi} + O\biggl(\frac{1}{n}\biggr) \\ &\qquad - \bigl(n - k + \tfrac{1}{2}\bigr)\log (n-k) + n - k - \log \sqrt{2\pi} + O\biggl(\frac{1}{n-k}\biggr) \\ &\qquad - \bigl(k - \tfrac{1}{2}\bigr)\log k + k - \log \sqrt{2\pi} + O\biggl(\frac{1}{k}\biggr) \\ &\qquad - \bigl(k + \tfrac{1}{2}\bigr)\log k + k - \log \sqrt{2\pi} + O\biggl(\frac{1}{k}\biggr) \\ &= (k-1)\log n - 2k\log k - \bigl(n - k + \tfrac{1}{2}\bigr)\log \biggl(1 - \frac{k}{n}\biggr) + k - \log (2\pi) + O\biggl(\frac{1}{\sqrt{n}}\biggr) \end{align}

for $k = \lfloor \sqrt{n+1}\rfloor = \sqrt{n} + O(1)$. With $k^2 = n + O(\sqrt{n})$ and a low-order Taylor expansion of the logarithms this leads to

$$\log p(n) \geqslant 2\sqrt{n} + O(\log n)$$

and hence

$$\liminf_{n \to \infty} \frac{\log p(n)}{\sqrt{n}} \geqslant 2\,,$$

from which

$$a := \inf \: \biggl\{ \frac{\log p(n)}{\sqrt{n}} : n \in \mathbb{N}\setminus \{0\}\biggr\} > 0$$

follows. Thus $p(n) \geqslant e^{c\sqrt{n}}$ holds e.g. for $c = a > 0$.