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.
 A: Note that
$$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.
A: 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.
A: My idea is quite similar to Barry Cipra's answer, but my solution does not require to discuss the cases for $2\leqslant n\leqslant9.$
The idea is just that, for each set $A$ in $S$, we can always find another positive number $k$ such that the sum of $k$ and the elements in $A$ is equal to $n$. Then, $A \cup \{k\}$ will be a partition of $n$. Now we need to prove that all of these partition sets formed are distinct. Then we are done.
Instead of considering the total sum of $1,2,...,\lfloor\sqrt{n}\rfloor$, let us look at the next maximum, i.e., the sum of $1,2,...,\lfloor\sqrt{n}\rfloor-1$, and try to find the $k$ for the set.
$$k =n-(1+2+\cdots+\lfloor\sqrt{n}\rfloor-1) = n-\frac{(\lfloor\sqrt{n}\rfloor-1)(\lfloor\sqrt{n}\rfloor)}{2} = n - \frac{\lfloor\sqrt{n}\rfloor^2}{2}+\frac{\lfloor\sqrt{n}\rfloor}{2}.$$
As $n = \sqrt{n}^{\,2}\geqslant \lfloor\sqrt{n}\rfloor^2$ and $n> \sqrt{n}$  for $n>1$, we have ,
$$k \geqslant \frac{n}{2}+\frac{\lfloor\sqrt{n}\rfloor}{2} >\lfloor\sqrt{n}\rfloor.  $$
Hence, for any set $A$ except $\{1,2,3,...,\lfloor\sqrt{n}\rfloor\}$, the new element $k$ will always be greater than $\lfloor\sqrt{n}\rfloor$. As a result, it is impossible for these sets to form identical partitions.
For the last set, $\{1,2,3,...,\lfloor\sqrt{n}\rfloor\}$, it is easy to see it contains all integers from $1$ to $\lfloor\sqrt{n}\rfloor$. However, from previous argument, all other partitions $A$ cannot contain all integers from $1$ to$\lfloor\sqrt{n}\rfloor$ as the new added element $k$ is always greater than $\lfloor\sqrt{n}\rfloor$ and thus cannot fill in the gap from $1$ to $\lfloor\sqrt{n}\rfloor$ in $A$.
Thus, all partitions formed are distinct. The proof is completed.
