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. 
 A: 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.
A: 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.
