Prove that the number of partitions of a number $n$ is less than the number of partitions of $n+1$. Now this seems quite trivial, but oddly enough, I'm not even sure how to go about proving it (ideally without generating functions since the question does not assume knowledge of them yet)?
Initially I thought of doing something along the lines of
$$ p(n+1) - p(n) > 0$$
and then proving by induction with base cases 1 and 2, however, I can't seem to not run in to generating functions for this...
Does anyone have any other insight on how to go about proving them? Ferrer's diagrams potentially?
Let $P_n$ denote the set of all partitions of $\{1,\ldots,n\}.$ Define a map $$f:P_n\to P_{n+1},\hspace{1cm} f(p_1,\ldots,p_k):=(1,p_1,\ldots,p_k)$$
Then $f$ is clearly injective, so $p(n)\leq p(n+1)$. However, $f$ is certainly not surjective since the trivial partition $(n+1)$ is not in the image of $f$. Therefore $p(n)<p(n+1)$.