Prove the identity involving summation and Stirling numbers of the second kind

429 Views Asked by At

Prove the identity $$(e^z-1)^m=m!\sum_{n}^{}{n \brace m}\frac{z^n}{n!}$$ $n\brace m$ stands for Stirling numbers of the second kind. I'm not really sure if $z$ is some special number or just an ordinary variable. And I have no clue on how to start.

Thanks!

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose you are allowed to use the OGF

$$F(z) = \sum_{n\ge m} {n\brace m} z^n = \prod_{r=1}^m \frac{z}{1-rz} = z^m \prod_{r=1}^m \frac{1}{1-rz}.$$

which seems like a reasonable assumption because it has a combinatorial proof.

Start by doing a partial fraction decomposition of the product term. We have with it being rational that $$\mathrm{Res}\left(\prod_{r=1}^m \frac{1}{1-rz}; z=\frac{1}{q}\right) = \prod_{r=1}^{q-1} \frac{1}{1-r/q} \times \left(-\frac{1}{q}\right) \times \prod_{r=q+1}^m \frac{1}{1-r/q} \\ = \left(-\frac{1}{q}\right) \times \prod_{r=1}^{q-1} \frac{q}{q-r} \times \prod_{r=q+1}^m \frac{q}{q-r} = - \frac{1}{q} q^{m-1} \frac{(-1)^{m-q}}{(q-1)! \times (m-q)!} \\ = - \frac{1}{m!} q^{m-1} (-1)^{m-q} {m\choose q}.$$

This gives for the OGF $F(z)$ that $$F(z) = -\frac{1}{m!} z^m \sum_{q=1}^m \frac{1}{z-1/q} q^{m-1} (-1)^{m-q} {m\choose q}.$$

In particular, $$[z^n] F(z) = {n\brace m} = -\frac{1}{m!} [z^n] z^m \sum_{q=1}^m \frac{1}{z-1/q} q^{m-1} (-1)^{m-q} {m\choose q} \\= \frac{1}{m!} [z^{n-m}] \sum_{q=1}^m \frac{q}{1-zq} q^{m-1} (-1)^{m-q} {m\choose q} \\ = \frac{1}{m!} \sum_{q=1}^m q^m q^{n-m} (-1)^{m-q} {m\choose q} = \frac{1}{m!} \sum_{q=1}^m q^n (-1)^{m-q} {m\choose q}.$$

To conclude introduce the EGF $$Q(z) = \sum_{n\ge 1} {n\brace m} \frac{z^n}{n!}$$ which is $$ \sum_{n\ge 1} \frac{z^n}{n!} \frac{1}{m!} \sum_{q=1}^m q^n (-1)^{m-q} {m\choose q}.$$

Interchanging the two summations this becomes $$ \frac{1}{m!} \sum_{q=1}^m (-1)^{m-q} {m\choose q} \sum_{n\ge 1} \frac{z^n q^n}{n!} = \frac{1}{m!} \sum_{q=1}^m (-1)^{m-q} {m\choose q} (\exp(qz)-1)$$

The term at $q=0$ is zero, so we get $$\frac{1}{m!} \sum_{q=0}^m (-1)^{m-q} {m\choose q} (\exp(qz)-1) = \frac{1}{m!} \sum_{q=0}^m (-1)^{m-q} {m\choose q} \exp(qz) \\ = \frac{1}{m!} (\exp(z)-1)^m.$$

The combinatorial proof of the OGF including some rather pedestrian work by this user can be found at this MSE link.