Proof of identity involving Stirling numbers of the second kind

Question

While computing conditional expectations of certain functionals of a Poisson white noise field (details are long and probably irrelevant), I've stumbled upon the need to use the following identity involving Stirling numbers of the second kind: $$ \ell{k\brace \ell} = \sum_{j=\ell}^k {k\choose j-1} (-1)^{k-j} {j\brace \ell}. $$ I used Manuel Kauers' Stirling package in order to produce a recurrence relation from which the identity can be easily proved. I still wonder, however, whether this is actually well-known, or there is some short proof...

Answer 1

You can give a short proof by interpreting the identity as an instance of inclusion-exclusion. The left hand side counts the number of ways of partitioning $S=\{1,2,\dots,k\}$ into $\ell$ parts and then picking one of the parts as the designated one.

Let $A_i$ denote the number of partitions of $S$ into $\ell$ parts where the designated part contains $i$. You can check that the left hand side is counting $|A_1\cup A_2\cup \cdots \cup A_k|$. For the right hand side notice that $$|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_r}|={k-r+1\brace \ell}$$ So by inclusion-exclusion we get $$|A_1\cup A_2\cup \cdots \cup A_k|=\sum_{r=1}^{k-l+1}(-1)^{r-1}\binom{k}{r}{k-r+1\brace \ell}$$ and reindexing by $j=k-r+1$ gives your identity.

Answer 2

The identity can be proved by equating coefficients of $z^k/k!$ in $$ l \frac{(e^z-1)^l}{l!}= (1-e^{-z}) \frac{d\ }{dz} \frac{(e^z-1)^l}{l!}.$$