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 ?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.