I've recently solved the problem:
Prove that
Is $S(n,k)= \sum_{r=k-1}^{n-1} \binom{n-1}{r} S(r,k-1)?$
I eventually proved the property but with my first approach I found a different expression and I was wondering whether they are equivalent or if I made a mistake somewhere.
My first approach was to "unwrap" the Stirling number on the LHS using the recurrence formula
$$S(n,k)=S(n-1, k-1)+kS(n-1, k)$$
This way, applying the formula on the second term of the sum $i$ times, I got:
$$S(n,k)=S(n-1, k-1)+kS(n-2, k-1)+ k^2S(n-3, k-1)+...+k^{i-1}S(n-i, k-1)+k^iS(n-i, k)$$
And applying it until the last term becomes $0$, I get:
$$S(n,k)=\sum_{r=k-1}^{n-1}k^{r-1}S(r, k-1)$$
Which at least at first glance looks different from what I wanted to prove.
Then, following a different approach I was able to prove the property as the problem puts it. However, this left me wondering whether both expressions are equal or if I made a mistake developing the first one.
Thanks in advance.
$$S(n,k)= \sum_{r=k-1}^{n-1} \binom{n-1}{r} S(r,k-1) \tag 1$$ is correct.
However, there is a slight mistake in the other recurrence.
\begin{eqnarray} S(n,k)&=&S(n-1,k-1)+kS(n-1,k) \\\ &=&S(n-1,k-1)+k(S(n-2,k-1)+kS(n-2,k)) \\ && \hspace{1cm} \vdots \\&=&\sum_{i=1}^{n-k+1} k^{i-1} S(n-i,k-1). \end{eqnarray} because if $i>n-k$, then $S(n-i,k)=0$.
We can rewrite this as $$S(n,k)=\sum\limits_{r=k-1}^{n-1} k^{n-1-r} S(r,k-1). \tag 2$$
These are both equivalent and are merely two ways of looking at the problem.
You want to partition the set $[n]$ into $k$ parts.
We can do this from $(k-1)$-set partitions of $[r]$ in a couple of ways.
$1)$ We can pick the elements that we do not want in the block that contains $n$ in $\binom{n-1}{r}$ ways and split it into a set partition with $k-1$ blocks in $S(r,k-1)$ ways.This gives $(1)$
$2)$ We can label the blocks according to the smallest number in that block. Label the boxes such that $i<j$ if the smallest element in $B_i$ is lesser than the smallest element in $B_j$. This forces the smallest element in $B_k$ to be at least $k$. We can now divide the sets based on smallest element in $B_k$.
Once we decide the smallest element of $B_k$ and it is $r+1$, say, we can then split the first $r$ elements into the remaining block $B_1,\dots,B_{k-1}$. This can be done in $S(r,k-1)$ ways. The elements that are greater than $r+1$, $r+2,r+3,\dots,n$ can then be put in any of the $k$ blocks and this can be done in $n-1-r$ ways. Since $r+1$ can range anywhere from $k$ to $n$, we get our count $2$.