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?
[Math] Upper and Lower Bound on Partition Function
integer-partitionsnumber theory
Related Solutions
The argument you give generalizes to show that $$p(n) \ge (k+1)^{ \lfloor \sqrt{ n/k } \rfloor }$$
for any positive integer $k$. We repeat the same argument, but instead of subsets of $\{ 1, 2, ... \lfloor \sqrt{n} \rfloor \}$ we allow multisubsets of $\{ 1, 2, ... \lfloor \sqrt{n/k} \rfloor \}$, where each element occurs with multiplicity $0$ through $k$.
So how much better is this? The actual asymptotic value of $\log p(n)$ is known to be $\pi \sqrt{ 2n/3 }$, so $C \sqrt{n}$ where $C \approx 2.565...$. The argument you give shows that $C \ge \log 2 \approx 0.693...$. The generalization above shows that $C \ge \frac{\log (k+1)}{\sqrt{k}}$. Some numerical experimentation shows that this attains a maximum at $k = 4$, giving $C \ge \frac{\log 5}{2} \approx 0.805...$. So this is a little better, but still a long way to go.
Edit #2: Here is an argument along the above lines which gives $C \ge \sqrt{2} \approx 1.414...$. We will now allow the positive integer $k$ to occur with a multiplicity from $0$ to $m_k - 1$ for some $m_k \ge 1$. This produces a partition in the same way as above provided that the sum constraint $\sum k (m_k - 1) \le n$ is satisfied, and we get $\prod m_k$ partitions this way. A heuristic calculation using Lagrange multipliers suggests that we want $m_k$ to be proportional to $\frac{1}{k}$; we will in fact take
$$m_k = \left\lfloor \frac{m}{k} \right\rfloor$$
if $k \le t$ (and $m_k = 1$ otherwise) for some $m, t$ satisfying certain constraints. First, since we must have $m_k \ge 1$, we need $m \ge t$. Second, the sum constraint $\sum k (m_k - 1) \le n$ gives
$$mt - \frac{t(t+1)}{2} \le n.$$
We will choose $m, t$ later. First, taking the logarithm of the number of partitions gives
$$\sum_{k=1}^t \log \left\lfloor \frac{m}{k} \right\rfloor.$$
We can write this as approximately (ignoring floors now)
$$\sum_{k=1}^t (\log m - \log k) = t \log m - \sum_{k=1}^t \log k.$$
(This is an overestimate but I believe it does not affect the asymptotic.) The estimate $\log n! \approx n \log n - n + O(\log n)$ gives that this is asymptotically
$$t \left( \log \frac{m}{t} + 1 \right) + O(\log t).$$
Now to optimize $m, t$. First, we can replace the sum constraint with a constraint
$$mt - \frac{t^2}{2} \le n$$
which is easier to deal with. Taking $t = a \sqrt{n}$ gives
$$m \le \left( \frac{1}{a} + \frac{a}{2} \right) \sqrt{n}$$
so we can just take $m$ to be this value (ignoring floors again); the constraint $m \ge t$ is now equivalent to the constraint $a \le \sqrt{2}$. The logarithm of the number of partitions we get now takes the form
$$a \sqrt{n} \left( \log \left( \frac{1}{2} + \frac{1}{a^2} \right) + 1 \right) + O(\log n)$$
which gives
$$C \ge a \left( \log \left( \frac{1}{2} + \frac{1}{a^2} \right) + 1 \right).$$
Some numerical experiments suggest that the RHS is increasing for $a \le \sqrt{2}$, and taking $a = \sqrt{2}$ gives $C \ge \sqrt{2}$ as desired.
I do not think this type of argument can be pushed substantially further without some new idea.
The proof of the asymptotic formula for the partition function given by Hardy and Ramanujan was "the birth of the circle method", and used properties of modular forms. Erdös was trying to give a proof with elementary methods (he also gave a so-called elementary proof of the PNT with Selberg). He succeeded in 1942 to give such a proof, but only with "unknown" constant $a$, see here. Afterwards Newman gave a "simplified proof", and obtained also that $a=\frac{1}{4n\sqrt{3}}$, see here.
There are several "modern" references now, which give an elementary proof of the asymptotic formula for $p(n)$. Here are two references:
M. B. Nathanson: On Erdös's elementary method in the asymptotic theory of partitions.
Daniel M. Kane (was misspelled as "Cane"): An elementary derivation of the asymptotic of the partition function.
Instead of using modular forms etc. the elementary method of Erdös only uses elementary estimates of exponential sums and an induction from the identity $$ np(n)=\sum_{ka\le n}ap(n-ka). $$
Best Answer
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}$$