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

Solution 1:

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}.$$

Solution 2:

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.