1
$\begingroup$

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.

$\endgroup$
  • 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 '16 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$ – bbn Apr 28 '16 at 15:38
  • 1
    $\begingroup$ @joriki Generating functions to the rescue. $\endgroup$ – Marko Riedel Apr 28 '16 at 22:11
1
$\begingroup$

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.

$\endgroup$
  • $\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$ – bbn Apr 29 '16 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.