A famous and simple lower bounds for Stirling numbers of the second kind is as follows:
$$\binom{n}{k-1} \le {n\brace k}$$
I tried to prove that using the relation $${n\brace k}=\frac{1}{k!}\sum_{j=0}^{k}\binom{k}{j}\left(-1\right)^{j}\left(k-j\right)^n$$
But could not conclude the result.Is it possible to prove this lower bound without using induction? ( If yes then please provide the proof, if no then use induction).
Also why we the lower bound does hold for this example: $$4=\binom{4}{3}+\binom{5}{3}\color{red}{\nleq}{4\brace 4}+{5\brace 4}=1$$
Suppose $k<n,$ consider a partition like $$\pi =\{B_1,\cdots, B_{k-1},B_k\},$$ such that $B_i=\{a_i\}$ and $1\leq a_1<a_1<\cdots <a_{k-1}\leq n,$ and $B_k=[n]\setminus \{a_1,\cdots ,a_{k-1}\}$ if $k<n,$ then $|B_k|>1$ so it is clear that this way produces an inclusion of $\binom{n}{k-1}$ in the partitions of $[n]$ into $k$ blocks, and the inequality is satisfied.
The problem with $k=n$ is that you are counting a lot of times($n$ times) the same partition(mainly $1/2/\cdots /n$).