Proof of equality $\sum_{k=0}^{m}k^n = \sum_{k=0}^{n}k!{m+1\choose k+1} \left\{^n_k \right\} $ by induction I have a problem with following equality:
$$\sum_{k=0}^{m}k^n = \sum_{k=0}^{n}k!{m+1\choose k+1} \left\{^n_k \right\} $$
And I would like to use induction in following way:
Base:
$$ m = n $$
And:
$$ (m, n) => (m + 1, n) \\
 (m, n) => (m, n + 1) $$
But When I try prove to base I get into trouble:
$$ \ \ \ m = n $$
$$\sum_{k=0}^{m} k^m=\sum_{k=0}^m k!{m+1\choose k+1}  \left\{ ^m_k \right\} $$
I can't see why this equality is true. Could you help me ?
 A: Your identity simply follows from the well-known fact that
$$ x^m = \sum_{j=0}^{m}j!{m\brace j}\binom{x}{j}$$
(see, for example, Graham-Knuth-Patashnik, p.262, or this survey by our beloved Mike Spivey) 
by summing over $x$, since:
$$\sum_{x=0}^{m}\binom{x}{j}=\binom{m+1}{j+1}.$$
A: We  can treat  this sum  using the  method of  annihilated coefficient
extractors.
Introduce the generating function
$$Q(z) = \sum_{m\ge 0} \frac{z^m}{m!} 
\sum_{j=0}^m j! \times  {m \brace j} \times  {x\choose j}$$
We require the bivariate  generating function of the Stirling numbers
of the second kind.
Recall the species for set partitions which is
$$\mathfrak{P}(\mathcal{U} \mathfrak{P}_{\ge 1}(\mathcal{Z}))$$
which gives the generating function
$$G(z, u) = \exp(u(\exp(z)-1)).$$
Substituting this generating function into $Q(z)$ we obtain
$$\sum_{m\ge 0} \frac{z^m}{m!} 
\sum_{j=0}^m j! \times  {x\choose j}
\times m! [z^m] [u^j]  \exp(u(\exp(z)-1))$$
which is
$$\sum_{m\ge 0} \frac{z^m}{m!} 
\sum_{j=0}^m j! \times  {x\choose j}
\times m! [z^m] \frac{(\exp(z)-1)^j}{j!}.$$
Switching summations now yields
$$\sum_{j\ge 0} {x\choose j} 
\sum_{m\ge j} z^m [z^m] (\exp(z)-1)^j.$$
The  inner sum  is  the promised  annihilated coefficient  extractor
(note that the formal power  series for $\exp(z)-1$ starts at $z$) and
hence everything simplifies to
$$\sum_{j\ge 0} {x\choose j} (\exp(z)-1)^j
= (\exp(z)-1+1)^x = \exp(zx).$$
It follows that
$$m! [z^m] Q(z) = m! \frac{x^m}{m!} = x^m.$$
There is another annihilated coefficient extractor at this 
MSE link I and another one at this 
MSE link II.
