Induction regarding Stirling numbers of the second kind.

Question

I was wondering how to prove this by induction $$S(m,m-1)=\frac{m(m-1)}{2}.$$ Any help is appreciative.

Answer 1

By the recurrence for the Stirling numbers, $$S(m,m-1)=S(m-1,m-2)+(m-1)S(m-1,m-1).$$ If you know what $S(m-1,m-1)$ is, this gives a basis for induction.

Answer 2

Assuming $S(m,m-1)$ is the Stirling number of the second kind, you need to partition $m$ elements into $m-1$ sets. This means that exactly one set has to contain $2$ elements, can you continue from here?

Answer 3

Recall, the Stirling numbers of the second kind $S(n,k)$ is the number of ways to partition a set of $n$ elements into $k$ distinct groups.

For this proof, we will use the recurrence $$S(n,k)=kS(n-1,k)+S(n-1,k-1).$$

Base case. Take $m=2$; then, we have $S(2,1)=1.$ There is only one way to partition a set of two elements in $1$ group. Also $2(2-1)/2=1.$ So this is fine.

Inductive hypothesis. Assume true for $m$; that is $$S(m,m-1)=\frac{m(m-1)}{2}.$$ Inductive step. Now, let's try it for $m+1$. We have \begin{align}S(m+1,m)&=mS(m,m)+S(m,m-1),\\ &=m+\frac{m(m-1)}{2},\\ &=\frac{2m+m^2-m}{2},\\ &=\frac{m^2+m}{2},\\ &=\frac{m(m+1)}{2}, \end{align} as required.

Do let me know if you are still confused with anything.