I have trouble proving the polynomials are identity:
$\sum_{k=0}^n {n \choose k}k^r x^k = \sum_{j=0}^{r} {n \choose j} j! (1+x)^{n-j} x^j S(r,j)$
$S(r,j)$ is a Stirling number of the second kind.
Although I tried hard, I cannot find even where I can start. Can anybody help me, please?
----edit
I am trying multidimensional induction, and I made it to show that it is true for n=p+1 and r=0 assuming the statement is true when $n=p$ and $r=0$. Now I should show it is true for $n=h$ and $r=q+1$ assuming the statement is true when $n=h$ and $r=q$. I know that I can start by differentiating it, but I am stuck on RHS.
In trying to verify
$$\sum_{k=0}^n {n\choose k} k^r x^k = \sum_{j=0}^r {n\choose j} j! (1+x)^{n-j} x^j {r\brace j}$$
we get for the coefficient on $x^k$ of the RHS
$$\sum_{j=0}^k {n\choose j} j! {n-j\choose k-j} r! [w^r] \frac{(\exp(w)-1)^j}{j!} \\ = r! [w^r] \sum_{j=0}^k {n\choose j} {n-j\choose k-j} (\exp(w)-1)^j$$
Here we are permitted to set the upper limit to $k.$ If $k\gt r$ the Stirling number produces zero for the extra values. If $k\lt r$ the values being omitted would have produced zero per ${n-j\choose k-j}.$
Observe that
$${n\choose j} {n-j\choose k-j} = \frac{n!}{j! \times (k-j)! \times (n-k)!} = {n\choose k} {k\choose j}$$
so we find
$${n\choose k} r! [w^r] \sum_{j=0}^k {k\choose j} (\exp(w)-1)^j = {n\choose k} r! [w^r] \exp(kw) = {n\choose k} k^r.$$
This is the claim.