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 ?

• Sorry, but what is $\left\{^n_k \right\}$? – The Great Seo Aug 11 '14 at 17:30
• Stirling number – xawey Aug 11 '14 at 17:34
• Stirling numbers of the second kind? – John Aug 11 '14 at 18:16
• There are about 1400 questions about proofs by induction. Try to choose a more descriptive title in the future. – user147263 Aug 11 '14 at 21:44
• Ok, Could somebody may show me how to prove it by induction ? – xawey Aug 18 '14 at 11:17

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

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.