I have this question regarding the Stirling Numbers of the Second Kind, $S(n,r).$ the question is "Prove that $\binom{n}{k-1}\leq S(n, k)\leq \binom{n-1}{k-1}k^{n-k}.$
For the upper bound, I used induction and the recursive formula $S(n+1,k)=S(n,k-1)+kS(n,k)$. The inductive step gives $$ S(n+1,k)=S(n,k-1)+kS(n,k)\leq \binom{n-1}{k-2}(k-1)^{n-k+1}+\binom{n-1}{k-1}k^{n-k+1} $$ and then used the equality $\binom{n-1}{k-2}+\binom{n-1}{k-1}=\binom{n}{k-1}$ to get the desired $S(n+1,k)\leq \binom{n}{k-1}k^{n+1-k}$.
However, I can't get the same to work for the lower bound... Maybe I'm just not seeing it right.
So my questions are...
a) Can the lower bound be proven this way?
b) Is there another way to prove both bounds? Is there some combinatorial argument I am not seeing?
c) Also. Why is combinatorics so hard. Why can't it behave nicely like other mathematics...
How about $$S(n+1,k)=S(n,k-1)+kS(n,k)\ge S(n,k-1)+S(n,k)\ge\binom{n}{k-2} +\binom{n}{k-1}=\binom{n+1}{k-1}?$$