inequality for stirling numbers of second kind

Question

How can I show that the following inequality hold: $$ S(n,k-1) \leq {k \choose 2}S(n,k), $$ where $k \leq n$ and $S(n,k)$ is the stirling number of second kind.

Answer 1

From each partition of $S(n,k-1)$ in turn we can form a partition of $S(n,k)$ by splitting a set with more than one element into two sets in an arbitrary way.

In this process some of the new partitions may well be duplicated. However, consider one of these new partitions. We can reform the original partition by combining two of the $k$ sets and so we can have at most ${k \choose 2}$ duplicates.

Therefore $S(n,k-1) \leq {k \choose 2}S(n,k)$.