$\Delta^d m^n =d! \sum_{k} \left[ m \atop k \right] { {k+n} \brace m + d}(-1)^{m+k}$ Is this a new formula? (EDIT: The variable $z$ is changed to $d$ so as not to be confused with generating function notation)
I have derived this formula involving the Stirling numbers that I now feel confident is correct (at least for non-negative integers $m$, $n$ and $d$).
$$\frac{\Delta^d m^n}{d!} = \sum_{k} \left[ m \atop k \right] { {k+n} \brace m + d}(-1)^{m+k}$$
(where the difference is taken with respect to $m$), giving the specific case for the plain exponent
$$m^n = \sum_{k} \left[ m \atop k \right] { {k+n} \brace m}(-1)^{m+k}$$
I am hoping that someone can provide a nice concise proof, as my proof involves a relatively lengthy path using a two dimensional induction argument just to show the formula for $m^n$. From there a straight application of the difference $$\Delta^d m^n = \Delta^{d-1}(m+1)^n - \Delta^{d-1}m^n$$ along with the identities $$\left[ m+1 \atop k \right] = m\left[ m \atop k\right] + \left[ m \atop k-1\right]$$ and $${ k+n \brace m+d} = { k+n+1 \brace m+d+1}  - ( m+d+1) { k+n \brace m+d+1} $$
leads to the general $d$-th difference formula.
This is in my opinion the nicest formula that I have seen involving both types of Stirling numbers, since it completely eradicates the powers. It is not a transformation from regular powers to falling powers/factorials, so maybe the formula could be used in situations where removing the exponent at the cost of adding the Stirling numbers is convenient. 
Does anyone care to make an attempt at giving a nice proof (or a reference)?

 A: What follows  is a proof that  is assembled from  various pieces which
we'll  link  to  in  order  not to  have  to  repeat  well-established
material.
We seek to evaluate
$$f_n = \sum_{k=1}^m
\left[m\atop k\right] {k+n\brace m} (-1)^{m+k}.$$
Following Wilf, we introduce the generating function
$$f(z) = \sum_{n\ge 0} f_n z^n.$$
We will have succeeded if we can show that
$$f(z) = \frac{1}{1-mz}$$
since $$[z^n] \frac{1}{1-mz} = m^n.$$
Observe that
$$f(z) = \sum_{n\ge 0} z^n \sum_{k=1}^m
\left[m\atop k\right] {k+n\brace m} (-1)^{m+k}
= \sum_{k=1}^m
\left[m\atop k\right] (-1)^{m+k}
\sum_{n\ge 0} {k+n\brace m} z^n.$$
We will do  the inner sum first. Recall  that the bivariate generating
function of the Stirling numbers of the second kind is given by
$$G(z, u) = \exp\left(u (\exp(z)-1)\right).$$
This implies for the sum that
$$\sum_{n\ge 0} {k+n\brace m} z^n
= \sum_{n\ge 0} z^n (k+n)! [z^{n+k}] \frac{1}{m!} (\exp(z)-1)^m.$$
Note that  the part after  the coefficient extraction operator  is the
generating function
$$\sum_{q\ge m} {q\brace m}\frac{z^q}{q!}.$$
Now this  is the  moment where we  need a subtle  observation concerning
generating functions.  If we  extract the coefficient $[z^{n+k}]$ from
an exponential generating function and  multiply by $(k+n)!$ we get the
value generated  by the EGF at  $k+n$. If we then  multiply by $z^n$
and sum over all $n$ we  get the ordinary generating function of these
values divided by $z^k.$ (Note that the exp term starts at $z$ and $m\ge k$
so it is safe to divide by $z^k.$ Furthermore we start extracting coefficients at $k$ and $k\le m$ so we can be sure that we get all of them.) 
This is a bit of a cognitive  leap but by no
means voodoo  of any sort. We  have simply observed  how a coefficient
extraction operator combined with a  summation can turn an EGF into an
OGF.
This OGF is well known however and is calculated e.g. at this MSE link. It is given by
$$z^m \prod_{q=1}^m \frac{1}{1-qz}.$$
Returning to $f(z)$ we thus obtain
$$f(z) = \sum_{k=1}^m
\left[m\atop k\right] (-1)^{m+k}
\frac{z^m}{z^k} \prod_{q=1}^m \frac{1}{1-qz}.$$
Moving parts that do not depend on $k$ to the front we get
$$(-1)^m z^m \times \prod_{q=1}^m \frac{1}{1-qz}
\times \sum_{k=1}^m
\left[m\atop k\right] \frac{(-1)^k}{z^k}.$$
Now note that the remaining sum is the ordinary generating function of
$\left[m\atop k\right]$ with respect  to $k$ evaluated at $-1/z.$ This
generating function is given by 
(consult e.g. Wikipedia)
$$\prod_{q=0}^{m-1} (x+q).$$
This gives for our sum
$$(-1)^m z^m \times \prod_{q=1}^m \frac{1}{1-qz}
\times \prod_{q=0}^{m-1} \left(-\frac{1}{z}+q\right)
= (-1)^m \times \prod_{q=1}^m \frac{1}{1-qz}
\times \prod_{q=0}^{m-1} \left(-1+qz\right)
\\ = \prod_{q=1}^m \frac{1}{1-qz}
\times \prod_{q=0}^{m-1} \left(1-qz\right)
\\ = \frac{1}{1-mz}$$
and we are done. Very nice identity indeed.
A: I have found a simple induction argument. For convenience let us introduce notation for the sum when $d=0$ by definition as
$$ \Theta_m^n = \sum_k \left[ m \atop k \right]{k+n \brace m} (-1)^{m+k}$$
The following will validate the recurrence
$$ m \Theta_m^n = \Theta_m^{n+1} + \sum_k \left[ {m+1} \atop k \right]{ k+n \brace m}(-1)^{m+k}$$
so that what will remain in order to prove $\Theta_m^n = m^n$ is to show the second sum is zero. (Note that $\Theta_m^0 = 1$ is true by the inversion formula which will complete the induction.)
Use the identity for the Stirling numbers of the first kind
$$ m\left[ m \atop k\right] = \left[ {m+1} \atop m\right] - \left[ m \atop {k-1}\right]$$
and we see that
$$
\begin{align}
m\Theta_m^n &= \sum_k \left[ {m+1} \atop k \right]{ k+n \brace m}(-1)^{m+k} -  \sum_k \left[ m \atop k-1 \right]{ k+n \brace m}(-1)^{m+k} \\
&= \sum_k \left[ {m+1} \atop k \right]{ k+n \brace m}(-1)^{m+k} -  \sum_k \left[ m \atop k \right]{ k+n+1 \brace m}(-1)^{m+k+1} \tag{1}\\
&= \sum_k \left[ {m+1} \atop k \right]{ k+n \brace m}(-1)^{m+k} +  \sum_k \left[ m \atop k \right]{ k+n+1 \brace m}(-1)^{m+k}\\
&= \sum_k \left[ {m+1} \atop k \right]{ k+n \brace m}(-1)^{m+k} +  \Theta_m^{n+1} \\
\end{align}$$
Can the sum be shown to be zero? I thought it was easy but not quite. See my other question
$$\sum_k \left[ {m+1} \atop k \right]{ k \brace m}(-1)^{m+k} = 0$$
The case $n=0$ is easy since
the only non-zero terms for this are when $k=m$ and $k=m+1$
$$\left[ m+1 \atop m\right] { m \brace m} - \left[ m+1 \atop m+1\right] { m+1 \brace m} = \left[ m+1 \atop m\right] \cdot 1 - 1\cdot  { m+1 \brace m}$$
This is zero since it is well known that
$$\left[ m+1 \atop m\right]  = { m+1 \brace m}$$
A: Consult the book Concrete Mathematics, Ronald L. Graham (Author), Donald E. Knuth (Author), Oren Patashnik (Author)
I'm almost certain that this or a very similar identity was in that book. They will not only prove but show how it is related to 15-thousand other identities you didn't think could possibly be proven! (it's a difficult and good read by the way... everyone should take some time to learn from that book IMAO)
