How to prove Eulerian Identity? 


This is a question in the book Concrete Mathematics of Graham and Knuth about Eulerian numbers, Stirling Numbers of the second kind and binomial coefficients. I have been thinking about it for a lot of time and failed to find out a way to solve it.
 A: By way of  enrichment and not necessarily following the  text we start
from the bivariate generating function  of the Eulerian numbers, which
seems like a reasonable starting point and which is
$$\frac{u-1}{u-\exp((u-1)z)}.$$
We seek to show that for $n\ge m$
$$m! {n\brace m} = \sum_{k=0}^{n-1}
\left\langle {n \atop k} \right\rangle
{k\choose n-m}.$$
The RHS is
$$[v^{n-m}] \sum_{k=0}^{n-1}
\left\langle {n \atop k} \right\rangle
(1+v)^k
\\ = n! [z^n] [v^{n-m}]
\frac{v}{1+v-\exp(vz)}
= n! [z^n] [v^{n-m}]
\frac{v}{v-(\exp(vz)-1)}
\\ = n! [z^n] [v^{n-m}]
\frac{1}{1-(\exp(vz)-1)/v}.$$
Now $\exp(vz)-1$ as a formal power series in $z$ starts
with $z$ and hence we may write
$$n!  [z^n] [v^{n-m}]
\sum_{q=0}^n \frac{(\exp(vz)-1)^q}{v^q}
=  [v^{n-m}]  n!  [z^n]
\sum_{q=0}^n \frac{(\exp(vz)-1)^q}{q!} \frac{q!}{v^q}
\\ = [v^{n-m}]
\sum_{q=0}^n {n\brace q} v^n \frac{q!}{v^q}
= [v^{n-m}]
\sum_{q=0}^n q! {n\brace q} v^{n-q}.$$
This is a polynomial in $v$ and only the term with $q=m$
contributes, namely
$$\bbox[5px,border:2px solid #00A000]{
m! {n\brace m}.}$$
A: Recall the well known formula for the Stirling numbers of the second kind
\begin{eqnarray*}
m! {n \brace m} = \sum_{i=0}^{m} (-1)^{m-i} \binom{m}{i} i^n
\end{eqnarray*}
the RHS is clearly the $m^{th}$ difference of the function $f(x)=x^n$.
So using $(6.37)$  and inverting the order of the plums, we have
\begin{eqnarray*}
m! {n \brace m} &=& \sum_{i=0}^{m} (-1)^{m-i} \binom{m}{i} i^n \\
&=& \sum_{i=0}^{m} (-1)^{m-i} \binom{m}{i} \sum_{k} \left\langle {n \atop k} \right\rangle \binom{i+k}{n} \\
&=& \sum_{k} \left\langle {n \atop k} \right\rangle \sum_{i=0}^{m} (-1)^{m-i} \binom{m}{i} \binom{i+k}{n}. \\
\end{eqnarray*}
Now a quick binomial identity using the old coefficient trick 
\begin{eqnarray*}
\sum_{i=0}^{m} (-1)^{m-i} \binom{m}{i} \binom{i+k}{n} &=& [x^n]: \sum_{i=0}^{m} (-1)^{m-i} \binom{m}{i} (1+x)^{i+k} \\
&=& [x^n]: x^{m}  (1+x)^{k} = \binom{k}{n-m}\\
\end{eqnarray*}
& we are dumb. $\ddot \smile$
