Upper and Lower Bound on Partition Function

Question

The partition function $p(n)$ counts the number of ways an integer can be expressed as a sum. For example, $p(4)=5$ as $$4=3+1=2+2=2+1+1=1+1+1+1$$ Hardy and Ramanujan were able to develop a converging series that provides us with an asymptotic expression for the partition function. However, it is quite complicated and therefore do not provide much insight regarding the ways in which this function behaves. Does there exist a simpler upper and lower bound for the partition function? If so, what are these bounds?

Answer 1

Hint

We know $p_k(n)$( partitions of $n$ into exactly $k$ parts) equals $$x_1+x_2+\cdots +x_k=n\quad ,\quad x_i\in \mathbb{N}$$

1. let $m=n+\left( \begin{matrix} k \\ 2 \\ \end{matrix} \right)$ and prove the number of distinct partition of $m$ into exactly $k$ distinct parts equals $p_k(n)$
2. show $$\frac{1}{k!}\left( \begin{matrix} n-1 \\ k-1 \\ \end{matrix} \right)\le {{p}_{k}}(n)\le \frac{1}{k!}\left( \begin{matrix} m-1 \\ k-1 \\ \end{matrix} \right)$$
3. Apply sigma notation for $k=1,2,\cdots n$