We have stumbled upon the following finite alternating sum, which we have trouble analyzing. The sum is:


$$
S\_n = \sum\_{j=0}^n \frac{ (-1)^j e^{-j} }{j!} (n-j)^j
$$


We have observed numerically that $S\_n \approx 2 n e^{-n}$. We would like to establish whether this conjecture is true. More precisely, we would like to show that $S\_n= \Theta(n e^{-n})$.


The sum is quite hard to evaluate numerically because the summands grow in absolute value initially and then decrease toward zero. The largest term is exponential in $n$ while the sum is conjectured to converge to zero exponentially fast. Any references or ideas are welcome!



A finite alternating sum
I have obtained a formula for the generating function of your sequence.


Let $S\_n$ be defined as in the quesion. We extend the definition to $n = 0$ by demanding $0^0 = 0$, hence $S\_0 = 0$.


Consider $S(t) = \sum\_{n\geq 0} S\_n t^n$. I will work out a formula for $S(t)$.


\begin{eqnarray\*}
S(t) &=& \sum\_{n=0}^\infty \sum\_{j = 0}^n\frac{(-e)^{-j}}{j!}(n - j)^j t^n\\
&=& \sum\_{j = 0}^\infty \frac{(-e)^{-j}}{j!}t^j\sum\_{n = 0}^\infty n^jt^n\\
&=& \sum\_{j = 0}^\infty \frac{(-e^{-1}t)^j}{j!}\frac{tA\_j(t)}{(1 - t)^{j + 1}}\\
&=& \frac{t}{1 - t}\sum\_{j = 0}^\infty A\_j(t)\frac{(\frac{e^{-1}t}{t - 1})^j}{j!}\\
&=& \frac{t}{1 - t}\frac{t - 1}{t - e^{e^{-1}t}}\\
&=& \frac{t}{e^{e^{-1}t} - t}.
\end{eqnarray\*}


Explanation for the calculation:


The key step is $\sum\_{n\geq 0} n^jt^n = \frac{tA\_j(t)}{(1 - t)^{j + 1}}$, where $A\_j(t)$ is the [Eulerian polynomial](https://en.wikipedia.org/wiki/Eulerian_number). We then use the generating function $\sum\_{j \geq 0}A\_j(t)\frac{x^j}{j!} = \frac{t - 1}{t - e^{(t - 1)x}}$.




---


It is then reasonable to make the change of variable $T = e^{-1}t$, which leads to $S\_n = e^{-n}S'\_n$, where the sequence $(S'\_n)\_n$ has generating function $\frac{eT}{e^T - eT}$. This at least gives a numerically better way to calculate the numbers $S\_n$.


And the question becomes to prove that $S'\_n = 2n + \frac{2}{3} + o(1)$, where $S'\_n$ is the $n$-th coefficient of the Taylor expansion of the function $\frac{T}{e^{T - 1} - T}$ at $T = 0$.


I'm however not able to proceed further...


One may try to subtract $\sum\_{n \geq 0}(2n + \frac{2}{3})T^n$, which is a rational fraction, and try to show that the difference has Taylor coefficients tending to $0$. But this doesn't seem to help much.


Also the $n$-th Taylor coefficient could be calculated via a residue at $0$, but again doesn't seem to help much.


Another observation is that $T = 1$ is a pole of the function $\frac{T}{e^{T - 1} - T}$.




---


Experimentally, it seems that the parameter $e$ is quite important. For this parameter, we indeed have $S'\_n = 2n + \frac{2}{3} + o(1)$, as Henri Cohen stated in the comment. In fact, the $o(1)$ is also exponentially decreasing.


If $e$ is changed to anything larger, then the sequence $(S'\_n)\_n$ increases much faster; if it is changed to anything smaller, then negative terms appear.


