A finite alternating sum

Question

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!

Answer 1

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

Answer 2

WhatsUp's generating function allows to get an asymptotics: we have $$\sum S_n t^n=\frac{t}{e^{t/e}-t},\sum S_n e^nt^n=\frac{t}{e^{t-1}-t}.$$ Denote $t-1=x$, then $$\frac{t}{e^{t-1}-t}=\frac{1+x}{e^x-1-x}=\frac{1+x}{x^2/2+x^3/6+\ldots}=\frac{2(1+x)}{x^2(1+x/3+\ldots)}=\frac2{x^2}+\frac{4/3}{x}+O(1)$$ for small $x$. Thus $$\frac{t}{e^{t-1}-t}=\frac2{(1-t)^2}-\frac{4/3}{1-t}+F(t)=\sum \left(2n+\frac23\right)t^n+F(t),$$ where $F$ does not have pole at 1. I claim that there is also no pole with absolute value at most 1, that is, the function $e^{t-1}-t$ does not have zeroes in the closed unit disc other than 1. Indeed, assume that $0\leqslant |r|\leqslant 1$ and $\varphi\in (-\pi,\pi]$ and $e^{re^{i\varphi}-1}=re^{i\varphi}$. Taking the arguments of both sides we get $r\sin \varphi=\varphi$ that yields $\varphi=0$, otherwise $|\varphi|>|\sin \varphi|\geqslant r|\sin \varphi|$. So $r=e^{r-1}\geqslant 1+(r-1)=r$ with equality only for $r=1$. This all implies that $F$ is analytic in a disc with radius greater than 1, therefore the coefficients of $F$ are $O(a^n)$ for certain $a\in (0,1)$ and in your question we get $$S_n=(2n+2/3)e^{-n}(1+O(a^n)).$$