Induction regarding Stirling numbers of the second kind. I was wondering how to prove this by induction $$S(m,m-1)=\frac{m(m-1)}{2}.$$ Any help is appreciative.
 A: 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.
A: 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?
A: 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.
