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.

  • $\begingroup$ I have changed my base case to 6, although how do I solve for S(6,3)? $\endgroup$ – jeremysanchez50 Nov 7 '15 at 20:36
  • $\begingroup$ 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. $\endgroup$ – Kevin Long Nov 7 '15 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.