Show that $S(n ,k)$... Show that
$$S(n,k) = \sum_{m = k-1}^{n-1} {n-1 \choose m} S(m,k-1)  $$
-I was having trouble with this proof in class and my professor suggested to look at it as another proof of the following theorem which states:
-For all $n\ge1$
$$B(n) = \sum_{k=0}^{n-1} {n-1 \choose k} B(k)  $$
-Unfortunately I still do not understand how to solve this proof, I do see the similarities in structure although I am brand new to Stirling numbers and am unsure of how this would affect the proof. Any help is appreciated.
 A: It may interest the reader to see how this can be done using generating functions.
Fixing the parameter $k$ we seek to show that
$${n\brace k} = \sum_{m=0}^{n-1} {n-1\choose m} {m\brace k-1}.$$
Here we have extended the summation back to zero because the second Stirling number produces zero for those extra values.
Recall the species for set partitions 
$$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$
which yields the generating function
$$G(z, u) = \exp(u(\exp(z)-1)).$$
It follows that the EGF of the LHS is
$$\frac{(\exp(z)-1)^k}{k!}.$$
Observe that when we  multiply two exponential generating functions of
the sequences $\{a_n\}$ and $\{b_n\}$ we get that
$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} 
\sum_{n\ge 0} b_n \frac{z^n}{n!}
= \sum_{n\ge 0} 
\sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\
= \sum_{n\ge 0} 
\sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!}
= \sum_{n\ge 0} 
\left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$
i.e. the  product of  the two generating  functions is  the exponential
 generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$
In the present case we have $A(z)=\exp(z)$ and
$$B(z) = \frac{(\exp(z)-1)^{k-1}}{(k-1)!}.$$
Therefore on the RHS we are extracting the coefficient
$$(n-1)! [z^{n-1}] \exp(z) \frac{(\exp(z)-1)^{k-1}}{(k-1)!}.$$
Integrating we see that this is
$$n! [z^n] \frac{(\exp(z)-1)^{k}}{k!},$$
the same as the LHS as claimed.
A: $S(n,k)$ is the number of partitions of the set $[n]=\{1,\ldots,n\}$ into exactly $k$ non-empty parts. Suppose that $\mathscr{P}$ is such a partition; then there must be a $P\in\mathscr{P}$ that contains the number $n$. 


*

*The other $k-1$ parts must contain at least $k-1$ and at most $n-1$ elements of $[n]$; why?  


Let $m=|[n]\setminus P|$, the number of elements of $[n]$ that are not in the same part of $\mathscr{P}$ as $n$.


*

*Show that there are $\binom{n-1}m$ ways to choose the elements that are not in the same piece as $n$.  

*Show that there are $S(m,k-1)$ ways to divide them into exactly $k-1$ non-empty parts.  


Now combine the pieces to get the desired identity.
