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

Question

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.

Answer 1

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.