Formula for $\sum_{k=0}^n S(n,k) k$, where $S(n,k)$ is a Stirling number of the second kind?

Question

I would like to compute $\sum_{k=0}^n S(n,k) k$, where $S(n,k)$ is a Stirling number of the second kind. Any ideas? It is like I am convolving the Stirling numbers of the second kind with the positive integers. Thank you very much!

Answer 1

$$\sum_{k=0}^n \left\{ n \atop k\right\} k = \varpi(n+1) - \varpi(n),$$ where $\varpi(n)$ is the $n$th Bell number.

Using generating functions, I prove this and the generalizations $$\sum_{k=0}^n \left\{ n \atop k\right\} k^m = \sum_{i=0}^m \binom{m}{i} R(m-i) \varpi(n+i),$$ $$\sum_{k=0}^n \left\{ n \atop k\right\} (-1)^k k^m = \sum_{i=0}^m \binom{m}{i} \varpi(m-i) R(n+i),$$ where $R(n)$ is the $n$th Rao-Uppuluri-Carpenter number, in the paper "On Solutions to a General Combinatorial Recurrence" (Journal of Integer Sequences 14 (9), Article 11.9.7, 2011). See Identities 12 and 13, which are at the very end. This paper has been submitted for publication, and I am still waiting on referee reports.

I don't know whether these results are new, but I had not seen them before. (They are not the main point of the paper.)

---

Added: Here are some additional derivations for $\sum_{k=0}^n \left\{ n \atop k\right\} k = \varpi(n+1) - \varpi(n)$. They are shorter than the one needed in the paper for the more general result.

First: Use the recurrence for the Stirling numbers of the second kind. (Due to OP - see comments.)

$$\sum_{k=0}^n \left\{ n \atop k\right\} k = \sum_{k=0}^n \left\{ n+1 \atop k\right\} - \sum_{k=0}^n \left\{ n \atop k-1\right\} = \sum_{k=0}^{n+1} \left\{ n+1 \atop k\right\} - \sum_{k=0}^n \left\{ n \atop k\right\} =\varpi(n+1) - \varpi(n).$$

Second: Use Bell polynomials $B_n(x)$.

It is known that $\sum_{k=0}^n \left\{ n \atop k \right\} x^k = B_n(x)$ (Eq. 14 on the linked page), $\frac{d}{dx} B_n(x) = \frac{B_{n+1}(x)}{x} - B_n(x)$ (Eq. 16), and $B_n(1) = \varpi(n)$ (Eq. 1). Thus

$$\sum_{k=0}^n \left\{ n \atop k\right\} k = \frac{d}{dx} \left.\sum_{k=0}^n \left\{ n \atop k\right\} x^k \right|_{x=1} = \frac{d}{dx} \left. B_n(x) \right|_{x=1} = \frac{B_{n+1}(1)}{1} - B_n(1) = \varpi(n+1) - \varpi(n).$$

Third: Use the double generating function for the Stirling numbers of the second kind (see, for example, Concrete Mathematics, 2nd edition, p. 351) $$\sum_{n,k \geq 0} \left\{ n \atop k\right\} w^k \frac{z^n}{n!} = e^{w(e^z-1)}.$$ (The right-hand side is actually the exponential generating function for the Bell polynomials, so this derivation is a variation on the second one.) Differentiating both sides with respect to $w$ and then letting $w = 1$ yields the exponential generating function (egf) for the sum in question: $$\sum_{n \geq 0} \left(\sum_{k=0}^n \left\{ n \atop k\right\} k \right) \frac{z^n}{n!} = e^{e^z-1} e^z - e^{e^z-1}.$$

It is known that $e^{e^z-1}$ is the egf for the Bell numbers. Since $e^z$ is the egf of the infinite sequence of $1$'s, and multiplication of exponential generating functions corresponds to binomial convolutions of the sequences in question, this means

$$\sum_{k=0}^n \left\{ n \atop k\right\} k = \sum_{k=0}^n \binom{n}{k} \varpi(k) - \varpi(n).$$ Finally, $\sum_{k=0}^n \binom{n}{k} \varpi(k) = \varpi(n+1)$ is a well-known identity for the Bell numbers, so we have $$\sum_{k=0}^n \left\{ n \atop k\right\} k = \varpi(n+1) - \varpi(n).$$