Stirling numbers of the second kind vs. binomial coefficient For $n,k$ positive integers, such that $n\geq k$, denote by $\left\{{n\atop      k}\right\} $ the Stirling numbers of the second kind and $\binom{n}{k}$ the binomial coefficient.
It is rather straightforward to prove that $\left\{{n\atop      k}\right\} \geq \binom{n}{k}$.
According to some calculation it looks like we also have $n^k\left\{{n\atop      k}\right\} \geq k^n\binom{n}{k}$.
I tried to prove this via induction using $\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} +
\left\{{n\atop k-1}\right\}$, but no luck. Any idea?
 A: Here is an induction proof.
First notice that  $$\tag 1 n^k\left\{{n\atop      k}\right\} \geq k^n\binom{n}{k}$$ is true for any $n$ when $k=1$  and for any $k$ when  $n=k$ , in which cases both sides are equal actually.
Let $n\ge 1$ and $n \ge p\ge 1$. The induction hypothesis is that $ m^k\left\{{m\atop      k}\right\} \geq k^m\binom{m}{k}$ is true (for all $k$) for all $m \le n$ and that $ (n+1)^k\left\{{n+1\atop      k}\right\} \geq k^{n+1}\binom{n+1}{k}$ is true for all $k \le p$.
A well-known generalised recursion for the Stirling numbers of the second kind is
$$ {n+1 \brace p+1}=\sum_{m=p}^n {n \choose m}{m \brace p} $$
Then
$$ {n+1 \brace p+1}\ge \sum_{m=p}^n {n \choose m}\frac{p^m}{m^p}{m \choose p}={n \choose p}\sum_{m=p}^n\frac{p^m}{m^p} {n-p \choose n-m} $$
that is
$$ {n+1 \brace p+1}\ge {n+1 \choose p+1}\frac{p+1}{n+1}\sum_{m=p}^n\frac{p^m}{m^p} {n-p \choose n-m} $$
$$ {n+1 \brace p+1}\ge {n+1 \choose p+1}\frac{(p+1)^{n+1}}{(n+1)^{p+1}}\frac{(n+1)^{p}}{(p+1)^{n}}\sum_{m=p}^n\frac{p^m}{m^p} {n-p \choose n-m} $$
whence
$$ {n+1 \brace p+1}\ge {n+1 \choose p+1}\frac{(p+1)^{n+1}}{(n+1)^{p+1}} $$
since
$$\frac{(n+1)^{p}}{(p+1)^{n}}\sum_{m=p}^n\frac{p^m}{m^p} {n-p \choose n-m} \ge 1$$
as is shown here.
A: Notice that $$k^n\binom{n}{k}=\sum _{j=1}^k\binom{n}{j}{n\brace j}j!\binom{n-j}{k-j},$$
this can be shown by realizing that the LHS counts the number of functions from $[n]$ to $[n]$ with image size less or equal than $k$ (say surjective on $j$ elements.) and you complete the image by choosing $k-j$ elements outside the image.
Also, we can use that $x^k = \sum _j {k\brace j}x^{\underline{j}}$to see $$n^k{n\brace k}=\sum _{j=1}^k\binom{n}{j}j!{k
\brace j}{n\brace k}.$$
Your inequality is then a consequence of
$${n\brace k}{k\brace j}\geq {n\brace j}\binom{n-j}{k-j}.$$
This last inequality can be checked by considering the following (The description is modulo bijections, for example in between $\binom{[n]}{k}$ and $\binom{X}{k}$ for $|X|=n$ so careful reading) function
$$f:{[n]\brace k}\times {[k]\brace j}\longrightarrow {[n]\brace j}\times \binom{[n-j]}{k-j},$$
defined by $f(\pi _1=\{A_1,\cdots,A_k\},\pi _2=\{B_1,\cdots,B_j\})=(\pi,X)$
with $$\pi = \left \{\bigcup _{x\in B}A_x:B\in \pi _2\right \},\, X = Min(\pi _2)\setminus Min(\pi),$$
where $Min(\pi):= \text{Set of minimum elements of each block in }\pi.$This function is surjective, consider $(\pi, X)$ with $X\cap Min(
\pi)=\emptyset$ and $|X|=k-j$ then just take $$\pi _1 =\{B\setminus X: B\in \pi
\}\cup \{\{x\}:x\in X\}$$ and $$\pi _2 = \{\{
a\}\cup\{x\in X:\text{x and a are in a block in }\pi\}:a\in Min(\pi)\}.$$
Check that $f(\pi _1,\pi _2)=(\pi,X).$
