An identity on Stirling number of the first and the second kind.

I have a difficulty in proving the identity

$\sum_{i=k}^n S(n+1,i+1)s(i,k) = \binom{n}{k}$

where $s(n,k)$ is the stirling number of the first kind and

$S(n,k)$ is the stirling number of the second kind.

I tried to show this equality by arguing a combinatorial interpretation but I failed. When I check this for $n=4, k=2$, I felt hard to interpret this in combinatorial situation.

And next, my second trial was using the generating function but I failed.

I prefer to have the combinatorial proof. However I need any comment to prove this identity. Please give me any advice. Thank you.

Suppose we seek to verify that $$\sum_{q=k}^n {n+1\brace q+1} (-1)^{q+k} \left[q\atop k\right] = {n\choose k}$$ where we have used Stirling numbers of the second and the first kind.

Introduce the generating function $$H(z) = \sum_{n=0}^\infty \frac{z^n}{n!} \sum_{q=k}^n {n+1\brace q+1} (-1)^{q+k} \left[q\atop k\right]$$

We have to show that this is $$\sum_{n=0}^\infty {n\choose k} \frac{z^n}{n!} = \sum_{n=k}^\infty {n\choose k} \frac{z^n}{n!} \\ = \sum_{n=0}^\infty {n+k\choose k} \frac{z^{n+k}}{(n+k)!} = \frac{z^k}{k!} \sum_{n=0}^\infty \frac{z^{n}}{n!} = \frac{z^k}{k!} \exp(z).$$

We extend $q$ back to zero because the Stirling number of the first kind is zero in the added range and start re-writing to get $$\sum_{n=0}^\infty \frac{z^n}{n!} \sum_{q=0}^n {n+1\brace q+1} (-1)^{q+k} \left[q\atop k\right] \\ = \sum_{q=0}^\infty \left[q\atop k\right] (-1)^{q+k} \sum_{n\ge q} {n+1\brace q+1} \frac{z^n}{n!}.$$

Recall the combinatorial class for set partitions which is $$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\mathcal{U} \times\textsc{SET}_{\ge 1}(\mathcal{Z}))$$ which gives the generating function $$G(z, u) = \exp(u(\exp(z)-1)).$$

which yields $$\sum_{n\ge 0} {n\brace q} \frac{z^n}{n!} = \frac{(\exp(z)-1)^q}{q!}.$$

Therefore $$\sum_{n\ge 0} {n+1\brace q} \frac{z^n}{n!} = \frac{(\exp(z)-1)^{q-1}}{(q-1)!} \exp(z).$$

This yields for the main generating function $$H(z) = \exp(z) \sum_{q=0}^\infty \left[q\atop k\right] (-1)^{q+k} \frac{(\exp(z)-1)^{q}}{q!}.$$

Recall furthermore the species of cycle decompositions $$\textsc{SET}(\mathcal{U} \times\textsc{CYC}_{\ge 1}(\mathcal{W}))$$

which gives the generating function $$G(w, u) = \exp\left(u\left(\log\frac{1}{1-w}\right)\right).$$

so that $$\sum_{q=0}^\infty (-1)^{q+k} \left[q\atop k\right] \frac{w^q}{q!} = (-1)^k [u^k] \exp\left(u\left(\log\frac{1}{1+w}\right)\right) \\ = \frac{(-1)^k}{k!} \left(\log\frac{1}{1+w}\right)^k.$$

This yields for $H(z)$ the closed form $$H(z) = \exp(z) \frac{(-1)^k}{k!} \left(\log\frac{1}{1+(\exp(z)-1)}\right)^k \\ = \exp(z) \frac{(-1)^k }{k!} \left(\log(1/\exp(z))\right)^k = \exp(z) \frac{(-1)^k (-1)^k z^k}{k!} \\ = \exp(z) \frac{z^k}{k!}$$

as claimed.

Remark. This all looks very familiar but I can't seem to locate the relevant post at this time.

Addendum. In order to be fully rigorous here we need to prove the formal power series identity $$\log\frac{1}{1+(\exp(z)-1)} = -z.$$

This is $$\sum_{q\ge 1} (-1)^q \frac{(\exp(z)-1)^q}{q}.$$

We see that there is no constant coefficient (so far so good) because $$\exp(z)-1 = z + \frac{1}{2}z^2 + \frac{1}{6} z^3 + \cdots$$

Moreover the only contribution to the coefficient on $z$ originates wth $q=1$ and is equal to minus one. It remains to show that for $m\gt 1$ the coefficient on $z^m$ is zero.

Re-write this as follows: $$[z^m] \sum_{q\ge 1} (-1)^q (q-1)! \frac{(\exp(z)-1)^q}{q!}. \\ = \sum_{q\ge 1} (-1)^q (q-1)! [z^m] \frac{(\exp(z)-1)^q}{q!} \\ = \sum_{q\ge 1} (-1)^q (q-1)! \frac{1}{m} [z^{m-1}] \frac{(\exp(z)-1)^{q-1}}{(q-1)!} \exp(z)$$

which yields for the sum

$$\frac{1}{m} [z^{m-1}] \exp(z) \sum_{q=1}^m (-1)^q (\exp(z)-1)^{q-1} \\ = - \frac{1}{m} [z^{m-1}] \exp(z) \sum_{q=1}^m (-1)^{q-1} (\exp(z)-1)^{q-1} \\ = - \frac{1}{m} [z^{m-1}] \exp(z) \frac{1-(1-\exp(z))^m}{1-(1-\exp(z))} \\ = - \frac{1}{m} [z^{m-1}] (1-(1-\exp(z))^m).$$

As before $1-\exp(z)$ has no constant term and hence $(1-\exp(z))^m$ starts at $(-1)^m z^m.$ Therefore we get $-1$ when $m=1$ and zero otherwise, which is the claim.

This concludes the argument.

Comment. It all depends which identities are to be accepted without proof. We get more work if we try to derive a result from the basics.

We have:

$$\sum_{i=k}^n (-1)^{i-k} {n+1\brace i+1} {i\brack k} = \sum_{i=k}^n (-1)^{i-k} {n+1\brace i+1} \left(\sum_{j=k}^i (-1)^{j-k} {i+1\brack j+1} {j\choose k}\right) = $$ $$ = \sum_{j=k}^n \left(\sum_{i=j}^n (-1)^{i-j}{n+1\brace i+1} {i+1\brack j+1} \right) {j\choose k} = \sum_{j=k}^n \delta_{n,j} {j\choose k} = {n\choose k} ,$$

with $n\brack k$ and $n\brace k$ being the Stirling number of the first and second kind respectively.