# Show that the number of partition of a natural number n, $p(n) ≥2^{\left \lfloor \sqrt n \right \rfloor}$ for $n\ge 2$.

Let $p(n)$ represent the number of partitions of a natural number n. Show that $p(n) ≥2^{\left \lfloor \sqrt n \right \rfloor}$ for $n \ge 2$ where $[x]$ represents the floor function, which takes any real number $x$ to the greatest integer equal to or less than $x$.

This is a problem from a practice exam and it gives a hint to construct a surjection from the set of partitions of n to the power set $\{1, 2, \ldots, \sqrt n \}$, but I'm really quite unsure about how to go about doing this. Any help would be greatly appreciated and I apologize for the poor formatting.

$$n-(1+2+\cdots+\lfloor\sqrt n\rfloor)=n-{\lfloor\sqrt n\rfloor(\lfloor\sqrt n\rfloor+1)\over2}\ge n-{\sqrt n(\sqrt n+1)\over2}={n-\sqrt n\over2}\gt\sqrt n\ge\lfloor\sqrt n\rfloor$$
if $n\gt9$. If $A$ is any subset of $S=\{1,2,\ldots,\sqrt n\}$ (for $n\gt9$), then $m=n-\sum_{k\in S}k\not\in S$ and $n=m+\sum_{k\in S}k$ is a partition of $n$. So the number of partitions of $n$ (for $n\gt9$) is at least the number of subsets of $S$, i.e., $p(n)\ge2^{\lfloor\sqrt n\rfloor}$. For $2\le n\le9$, the inequality can be verified case by case.
Hint: Each set $A$ in the power set of $S$ represents for at least one partition of $n$ that contains all elements in $A$ (each appears at least once in the partition) but no element in $S \setminus A$ appears in the partition.
• What is the set $S$? – TheNotMe Dec 25 '17 at 20:12