A sum of Stirling numbers of the second kind

Question

Find a formula (either exact or asymptotic in $N$) for $S(N)$, where \begin{equation} S(N) = \sum_{n=N}^\infty \sum_{k=N}^n \sum_{j=0}^k \binom{k}{j} (-1)^{k-j} (1+j)^n \frac{t^n}{n!}. \end{equation} Here $N\geq 1$, $\binom{k}{j}$ is the combinatorial symbol, and $t$ is a formal parameter.

Note: perhaps it is useful to recall the Stirling numbers of the second kind, \begin{equation} \left\{ \begin{array}{c} n \\ k \end{array} \right\} = \frac{1}{k!} \sum_{j=0}^k \binom{k}{j} (-1)^{k-j} j^n, \end{equation} and their generating function \begin{equation} \sum_{n=0}^\infty \left\{ \begin{array}{c} n \\ k \end{array} \right\} \frac{x^n}{n!} = \frac{(e^x-1)^k}{k!}. \end{equation}

I appreciate comments regarding special functions, asymptotic techniques, or references that could be useful to solve this problem.

Answer 1

Suppose we seek to evaluate

$$S(N) = \sum_{n=N}^\infty \sum_{k=N}^n \sum_{j=0}^k {k\choose j} (-1)^{k-j} (1+j)^n \frac{t^n}{n!}.$$

This is

$$S(N) = \sum_{n=N}^\infty \frac{t^n}{n!} \sum_{k=N}^n \sum_{j=0}^k {k\choose j} (-1)^{k-j} (1+j)^n.$$

Now introduce

$$(1+j)^n = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((1+j)z) \; dz.$$

We thus get for the inner sum

$$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{j=0}^k {k\choose j} (-1)^{k-j} \exp((1+j)z) \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(z)}{z^{n+1}} (\exp(z)-1)^k\; dz.$$

Substitute this into the middle sum to get

$$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(z)}{z^{n+1}} \frac{(\exp(z)-1)^{n+1} - (\exp(z)-1)^N}{\exp(z)-2} \; dz.$$

Now since $\exp(z)-1$ starts at $z$ the first term drops out and we get

$$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(z)}{z^{n+1}} \frac{(\exp(z)-1)^N}{2-\exp(z)} \; dz.$$

We thus get for the remaining sum

$$\sum_{n=N}^\infty \frac{t^n}{n!} \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(z)}{z^{n+1}} \frac{(\exp(z)-1)^N}{2-\exp(z)} \; dz.$$

Finally note that $(\exp(z)-1)^N$ starts at $z^N$ so we may lower the initial value of the remaining summation to zero, getting

$$\sum_{n=0}^\infty t^n \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(z)}{z^{n+1}} \frac{(\exp(z)-1)^N}{2-\exp(z)} \; dz.$$

What we have here is an annihilated coefficient extractor which finally yields

$$\frac{\exp(t)}{2-\exp(t)} (\exp(t)-1)^N.$$

Now for the exponential growth rate of the coefficients on $t^n$ we get the distance to the nearest singularity which is $\log 2.$ So the radius of convergence of this sum is $|t|<\log 2.$

Observation. Having reached the end of this computation we see that we didn't need to substitute the variable in the integral, which means we could have used the coefficient extractor notation $[z^n]$ throughout. This does not affect the semantics of the computation.

Remark. There are several more examples of the technique of annihilated coefficient extractors at this MSE link I and at this MSE link II and also here at this MSE link III.