In this question we consider the partition function $p(n)$ – that is, the number of ways to express $n$ as a sum of positive integers.
One easy exercise is to show that $$ p(n) \geq 2^{\lfloor \sqrt{n} \rfloor}$$ for all $n > 1.$
The bound is rather stupid since one just takes a subset of $\{1,\ldots,\lfloor \sqrt{n} \rfloor \}$ and assigns to it a partition of $n$ in the natural way. So every partition is of a very specific way.
I was wondering what are some others lower bounds for $p(n)$ one could derive as an exercise using just elementary combinatorial and number theoretical facts ? What is the next bound one could try to obtain after the stated one?
This is meant just for practice otherwise one could readily use Hardy and Ramanujan’s results about the asymptotic of $p(n).$
Best Answer
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.