Wikipedia states that Stirling numbers of the second kind satisfy the following relation:
$$\sum_{n\ge0}^{ }n^{m}z^{n}=\sum_{j=0}^{m}{m+1\brace j+1}\frac{\left(-1\right)^{m-j}j!}{\left(1-z\right)^{j+1}}$$
I know a similar relation which is as follows:
$$n^{m}=\sum_{j=0}^{m}{m\brace j}\binom{n}{j}j!\tag{$n,m\ge0$}$$
From here we have: $$\sum_{n=0}^{r}n^{m}=\sum_{n=0}^{r}\sum_{j=0}^{m}{m\brace j}\binom{n}{j}j!$$
Using Hockey-stick identity the expression transforms to:
$$\sum_{n=0}^{r}n^{m}=\sum_{j=0}^{m}{m\brace j}\binom{r+1}{j+1}j!$$
However the first one is new to me,can someone please give me a combinatorial and an algebraic way to proof of that?I wonder how using generating functions (possibly) and some combinations it can be proved.
In seeking to prove that
$$\sum_{n\ge 0} n^m z^n = \sum_{j=0}^m {m+1\brace j+1} \frac{(-1)^{m-j} j!}{(1-z)^{j+1}}$$
we require by extraction of the coefficient on $[z^n]$ that
$$n^m = \sum_{j=0}^m {m+1\brace j+1} (-1)^{m-j} j! {n+j\choose j}$$
The RHS is by standard EGFs
$$(m+1)! [z^{m+1}] \sum_{j=0}^m \frac{(\exp(z)-1)^{j+1}}{(j+1)!} (-1)^{m-j} j! {n+j\choose j} \\ = m! [z^m] \exp(z) \sum_{j=0}^m \frac{(\exp(z)-1)^{j}}{j!} (-1)^{m-j} j! {n+j\choose j} \\ = m! [z^m] \exp(z) \sum_{j=0}^m (\exp(z)-1)^{j} (-1)^{m-j} {n+j\choose j}.$$
Now because $(\exp(z)-1)^j = z^j+\cdots$ there is no contribution to the coefficient extractor $[z^m]$ when $j\gt m$ and we may extend the sum to infinity:
$$m! (-1)^m [z^m] \exp(z) \sum_{j\ge 0} (\exp(z)-1)^{j} (-1)^j {n+j\choose j} \\ = m! (-1)^m [z^m] \exp(z) \frac{1}{(1+\exp(z)-1)^{n+1}} \\ = m! (-1)^m [z^m] \exp(z) \exp(-(n+1)z) \\ = m! (-1)^m [z^m] \exp(-nz) = m! [z^m] \exp(nz) = n^m.$$
This is the claim.