How to prove $ \lim_{n \to \infty} e^n \cdot \left( \sum_{k=0}^{n-1} ({k-n \over e})^k/k! \right)- 2 \cdot n = \frac 23$?

Solution 1:

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.

Solution 2:

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 https://mathoverflow.net/questions/141368/error-term-for-renewal-function discusses the behaviour of the error term $\epsilon(n) = f(n) - 2n - 2/3$.

Solution 3:

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.