Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I observed for the function $$ f(n)= e^n \sum_{k=0}^{n-1}\left(\dfrac{k - n}{e}\right)^k \cdot \dfrac{1}{k!} \tag 1$$

with small $n$ that

  n  sum
  1  2.7182818
  2  4.6707743
  3  6.6665656
  4  8.6666045
  5  10.666662
  6  12.666667
  7  14.666667
  8  16.666667

So an obvious hypothesis is $$ \lim_{n \to \infty} \bigl(f(n)-2n\bigr) = \frac 23 \tag 2$$

However, I have no idea, how to prove this but would like to understand how I can approach such a proof (I'll have then some similar ones with likely the same or related logic)

So I would like to understand ...

Q: how I could prove that assumed limit (2).

share|improve this question
the title is certainly wrong: you can't have a limit in $n$ which is a function of $n$. –  Alex Jun 23 '14 at 7:27
@Alex, Just consider $$\lim_{n \to \infty} -2n + e^n \sum_{k=0}^{n-1} ({k-n \over e})^k/k! = \frac 23$$ –  Fabien Jun 23 '14 at 7:31
what you wrote may be correct. The title is certainly not. –  Alex Jun 23 '14 at 7:33
@Alex: I got it, thanks! Just edited the title. –  Gottfried Helms Jun 23 '14 at 7:54

3 Answers 3

This is a pretty neat problem actually so I'm only giving you a little hint. Start by rewriting as $$\sum_{k=0}^{n-1}\frac{1}{k!}(k-n)^{k}e^{-(k-n)}=\sum_{k=0}^{n-1}\frac{1}{k!}\frac{d^{k}}{dx^{k}}e^{x(k-n)}|_{x=-1}=\sum_{k=0}^{n-1}\frac{1}{2\pi i}\int_{C}\frac{e^{z(k-n)}}{(z+1)^{k+1}}dz$$

Since $e^{z(k-n)}$ is analytic in all of $\mathbb{C}$ I applied Cauchys Integral formula and $C$ denotes an appropriate cirle that encloses the multiple singularity $z=-1$

Now feel free to expand further to a geometric sum and you shouldn't be too far from a final solution.

share|improve this answer
Very neat -thank you! Only I'm illiterate with that type of integral so I do not know how to proceed here (and more: I doubt I can use/adapt this idea by myself to the other cases in my set of limit-epressions). I know I can look in wikipedia (and have done this from time to time earlier) for the Cauchy integral or circular/path integral but I've never got the key idea of it and how to operate with it actually... –  Gottfried Helms Jun 23 '14 at 12:18
So after bringing the sum inside and simplifying we are left with $\frac{1}{2\pi i} \int_C \frac{dz}{(1+z)^n(e^z - z - 1)}$. How do you see that this is close to $2n + \frac{2}{3}$? –  J. J. Jun 23 '14 at 12:30
Perhaps it is useful to know, that I got that $f(n)$ as partial sums (always up to $n$) of a transform of the geometric series (with $q=1$), which must somehow be related to the Borel-summation method. Also in the analysis of the Borel-summation I've seen the consideration of an integral, however I don't know whether it is related. But perhaps this loose relation contains another clue? –  Gottfried Helms Jun 23 '14 at 13:42

One can notice that your formula is the expected number of $[0,1]$-uniformly distributed random variables that are needed for their sum to exceed $n$. (See http://mathworld.wolfram.com/UniformSumDistribution.html.) Moreover, the question http://mathoverflow.net/questions/141368/error-term-for-renewal-function discusses the behaviour of the error term $\epsilon(n) = f(n) - 2n - 2/3$.

share|improve this answer
Wow, what an incidence (the MO-question)! The formula occurs by the matrix-summation-method based on the "Eulerian numbers" and of which I've asked&discussed several aspects (also here and in MO). Now it would be interesting whether also the generalizations might have similar relatives like that in the MO-question... –  Gottfried Helms Jun 23 '14 at 15:16
I've just put some background-information from my work with this at the MO-site's question, which you've linked to. Perhaps this is interesting,too –  Gottfried Helms Jun 24 '14 at 2:40

Notice that $$f'(n) = f(n) - f(n-1)$$

so this is a simple (but special) case of a delay differential equation. Simply substituting $f(n) = e^{an}$ reveals the form of the general solution: $$\sum_{-\infty}^{\infty} c_k e^{(1 + W_k(-\frac{1}{e}))n}$$

where $W_k(x)$ is the k-th branch of the LambertW function, and $c_k$ are parameters depending on the boundary conditions.

To get the solution we must take into account the double root at $k=-1,0$, where $W_{-1}(-\frac{1}{e}) = W_0(-\frac{1}{e}) = -1$:

$$f(n) = (c_{-1} +c_0n)e^0 + \sum_{-\infty,\neq 0,-1}^{\infty} c_k e^{(1 + W_k(-\frac{1}{e}))n}$$

but from definition $$e^{1+W_k(-\frac{1}{e})} = -\frac{1}{W_k(-\frac{1}{e})}$$ and $|\!|W_k(-\frac{1}{e})|\!| > 1$ for $k\neq, 0, -1$, so

$$\lim_{n\to\infty} f(n) = c_{-1} + c_0n + 0$$

See here for a solution that uses Laplace transform.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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