Relation between Binomial coefficient and Stirling number of second type

Question

Is that true, that for every n,k such that $$k>1$$ we have the inequality $${n \choose k} \leq {n \brace k}$$?

Answer 1

This is true by induction on $n$ using the recurrence $\displaystyle {n+1 \brace k} = {n \brace k-1} + k{n \brace k}$.

For $k=2$: $\displaystyle {n+1 \brace 2} = {n\brace 1} + 2{n \brace 2} \geq 1 + 2\binom{n}{2} \geq \binom{n+1}{2}$ by induction. For $k=n$, $\displaystyle {n\brace n} = 1 = \binom{n}{n}$. For other $k$, $\displaystyle {n+1 \brace k} = {n \brace k-1} + k{n \brace k} \geq \binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}$ by induction.