# Prove the lower bound $\binom{n}{k-1} \le {n\brace k}$

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$$

• Unless I am mistaken, ${4\brace 4}+{5\brace 4} = 1 + 10 = 11$ – Martin R Mar 20 '20 at 10:39
• Does this answer your question? A property of Stirling Numbers of the Second kind (Combinatorics related) – Martin R Mar 20 '20 at 10:42
• @ Martin R,but is not ${n\brace n-1}=\binom{n}{2}$? – user715522 Mar 20 '20 at 10:43
• @ Martin R , the link does not provide a proof without using induction) – user715522 Mar 20 '20 at 10:44
• $\binom{n}{k-1} \le {n\brace k}$ is apparently wrong for $k=n > 1$. – Martin R Mar 20 '20 at 10:54

## 1 Answer

Suppose $$k consider a partition like $$\pi =\{B_1,\cdots, B_{k-1},B_k\},$$ such that $$B_i=\{a_i\}$$ and $$1\leq a_1 and $$B_k=[n]\setminus \{a_1,\cdots ,a_{k-1}\}$$ if $$k 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$$).

• @ Phicar,what does the left hand side tell us? – user771003 May 22 '20 at 8:42
• @user715522 It tells us the number of partitions of this form that i wrote down. But because they are not all the partitions possible, then the inequality holds. Unless, clearly, if $n=k.$ – Phicar May 22 '20 at 12:50