Prove superpolynomial growth rate

Question

Let $p(n)$ be the number of partitions of $n$.

Prove that growth rate of $p(n)$ is superpolynomial, meaning that for every given $k$ there is $p(n)= \omega (n^k)$.

Answer 1

Given $k$, the number of compositions of $n$ into $k+1$ parts is $\binom{n+k}k$, which is a polynomial of degree $k$ in $n$. The number of partitions of $n$ into $k+1$ parts is at least $\frac1{(k+1)!}$ times the number of compositions. This gives the required order of growth only considering partitions into $k+1$ parts, which of course is a lower bound for the total number of partitions.