Stirling number of the second kind recurrence relations

Question

I am interested to understand why the following recurrence relations of the Stirling number so the second kind hold using counting arguments (http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind): \begin{align*} S_{n+1,k+1} &= \sum_{j=k}^n \binom{n}{j} S_{j,k} \\ S_{n+1,k+1} &= \sum_{j=k}^n (k+1)^{n-j} S_{j,k} \\ S_{n+k+1,k} &= \sum_{j=0}^k j S_{n+j, j} \end{align*}

Answer 1

Hint for the first two:
1)Fix the (n+1)th-element in one class. You want to construct every possibility for that particular class. So you want the cases when that class has 1 element, 2 elements, etc...So, if you want j elements in that class, you must choose j-1 elements of the n remaining and the other n-1-(j-1) elements must be divided in other k classes.

2)Fix the (n+1)th-element in the one class. Think that $(k+1)^{n-j}$ says, combinatorially, that you want to assign to those n-j elements one of the k+1 possible colors.