TITLE: Evaluate sum involving stirling numbers of second kind using EGF
QUESTION [2 upvotes]: We have the following identity for Stirling numbers of second kind:
$${{n+1}\brace{m+1}} = \sum_{k=m}^{n}{n\choose k}{{k}\brace{m}}$$
I know how to prove that combinatorially, but I want to know, how to get the LHS just evaluating the sum in the RHS. Recently I've been introduced to EGFs and I see, that sum in RHS is a binomial convolution. So we have (EGF for Stirling numbers multiplied by EGF for the sequence of 1):
$$\frac{(e^t-1)^m}{m!}e^t$$
What is the next step? How to use this EGF to evaluate the sum?

REPLY [2 votes]: $$\begin{align*}
\frac{(e^t-1)^m}{m!}\cdot e^t&=\frac{(e^t-1)^{m+1}}{m!}+\frac{(e^t-1)^m}{m!}\\
&=(m+1)\left(\frac{(e^t-1)^{m+1}}{(m+1)!}\right)+\frac{(e^t-1)^m}{m!}\\
&=(m+1)\sum_{k\ge 0}{k\brace{m+1}}x^k+\sum_{k\ge 0}{k\brace m}x^k\\
&=\sum_{k\ge 0}\left((m+1){k\brace{m+1}}+{k\brace m}\right)x^k\\
&=\sum_{k\ge 0}{{k+1}\brace{m+1}}x^k
\end{align*}$$
{"set_name": "stack_exchange", "score": 2, "question_id": 2002259}