# Prove by induction that $S(n,3) > 3^{n-2}$ for all $n≥6$

Prove by induction that $S(n,3) > 3^{n-2}$ for all $n≥6$

I have done the base case for this problem, using $n=6$ as my base case: $$S(6,3) > 3^{6-2}$$

$$S(6,3) > 81$$

-I am brand new to Stirling numbers and am unsure as to how to confirm this base case, and how to move forward with the rest of the problem. Any help is appreciated.

It doesn't really make sense to have base case $n=2$ if you're proving it for $n \geq 6$. Start with the base case, $n=6$ and $n=7$ and prove each of those. From there, for any $k \geq 6$, you assume it true for $n=k$ and $n=k+1$ and can prove it for $n=k+2$ you can use the recurrence relation $S(n+1,k)=k*S(n,k)+S(n,k-1)$ and then invoke the inductive hypothesis.
• It's a bit tedious, but you can, again, use the recurrence relation and the fact that for all $n$, $S(n,n)=1$. That part isn't really the meaningful part of the proof, just the necessary base step so that you can perform induction. Just so you can check, I will state that $S(6,3)=90$ and $S(7,3)=301$ so the base step holds. – Kevin Long Nov 7 '15 at 23:39