# A finite alternating sum

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!

• Section 1.2.11.3 of volume 1 of The Art of Knuth contains very similar sums, and the techniques there should give you your answer $(2n+2/3+o(1))e^{-n}$, but I haven't worked out the details. – Henri Cohen Oct 27 '19 at 23:19
• @Henri, "The Art of Knuth"? – Gerry Myerson Oct 28 '19 at 4:30
• "The art of computer programming" by Knuth, most likely. – jamesh625 Oct 31 '19 at 22:48

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.

• Thank you! I was not familiarized with Eulerian polynomials. I really enjoyed learning about this and the approach. – Francisco Oct 30 '19 at 5:27
• You do not actually need Euler polynomials: for fixed $n$ we get $\sum_j (-e)^{-j}n^j t^j/j!=\exp(-nt/e)$, then summing by $n$ we have $\sum_n \exp(-nt/e)t^n=\sum_n (t\exp(-t/e))^n=1/(1-t\exp(-t/e))$, hm, this slightly differs from yours formula. Let's check the coefficients of $t^0$. – Fedor Petrov Oct 30 '19 at 7:45
• For $j=0$ the equality $\sum_{n\geq 0}n^j t^j=\frac{t A_j(t)}{(1-t)^{j+1}}$ uses the convention $0^0:=0$. With $0^0:=1$ you arrive at Fedor Petrov's result. – esg Oct 30 '19 at 16:24

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

• Are the smallest zeros at $\approx 3.088843015613\pm 7.461489285654i$? – MyNinthAccount Oct 28 '19 at 8:32
• No idea. It is possible to find them of course with any accuracy using computer software. – Fedor Petrov Oct 28 '19 at 8:48
• Ah! Seems I was almost there (: Great job! – WhatsUp Oct 28 '19 at 9:29
• Indeed, very nice. Thank you! – Francisco Oct 30 '19 at 5:27