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.

  • 1
    $\begingroup$ This could be a start: \begin{align} 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!}\\ &=\sum_{n=N}^\infty \sum_{k=N}^n \sum_{j=0}^k \binom{k}{j} (-1)^{k-j} \sum_{l=0}^n\binom nlj^l \frac{t^n}{n!}\\ &=\sum_{n=N}^\infty \sum_{k=N}^n \sum_{l=0}^n\binom nl\frac{t^n}{n!}\sum_{j=0}^k \binom{k}{j} (-1)^{k-j}j^l \\ &=\sum_{n=N}^\infty \sum_{k=N}^n \sum_{l=0}^n\binom nl\frac{t^n}{n!}k!\left\{l\atop k\right\}\\ \end{align} $\endgroup$
    – joriki
    Apr 28, 2016 at 12:26
  • $\begingroup$ @joriki, this is certainly useful. The sum of the Stirling numbers weighted with $k!$ look the the ordered Bell numbers en.wikipedia.org/wiki/Ordered_Bell_number $\endgroup$
    – mforets
    Apr 28, 2016 at 15:38
  • 1
    $\begingroup$ @joriki Generating functions to the rescue. $\endgroup$ Apr 28, 2016 at 22:11

1 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.

  • $\begingroup$ This is exactly what I was looking for, I appreciate very much your detailed answer and the links, thanks. By the way, I came up with this type of sum since I am trying to evaluate the error term in a numerical method (of order $N$) I am working at. $\endgroup$
    – mforets
    Apr 29, 2016 at 6:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .