How can we prove this using combinatorial argument?
$$S_{n+1,k+1} = \sum_{j=k}^n (k+1)^{n-j} S_{j,k}$$
I tried to solve this by fixing the last element to be $k+1$-th partition, and making $j$ elements to have $k+1$ choice of partitions, but I don't know how to create $S_{j,k}$ ways without repeating the same partition. Any idea will be appreciated.
The term $(k+1)^{n-j} S_{j,k}$ corresponds to a situation where $j$ elements are partitioned into $k$ non-empty subsets, and then $n-j$ are free to be placed independently in any of the $k+1$ subsets. That leaves one element unaccounted for, and one subset which we need to guarantee to be non-empty.
Suppose we assign the elements to sets in order. At the point at which all subsets are non-empty, we're free to assign the rest. So rather than fixing the last element, the key is to focus on the first element assigned to the last part.