Lemma: Let be the number of ordered partitions of a set of n elements in k sets. - or the number of ways in which you can distribute n balls into k boxes -
Let's compute the coefficient of of the RHS.
Since it follows that our coefficient is:
Now: and each term is the number of ordered permutations in which you can have elements in box number 1, ... -permutations with repetition -
So the coefficient is actually
Next note that -the LHS is the stirling number of the second kind, or, the number of partitions of a set of n elements into k sets (here we do not care about the order) -
Hence: and summing over k :
Since: we are done