17
$\begingroup$

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!

$\endgroup$
  • 12
    $\begingroup$ 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. $\endgroup$ – Henri Cohen Oct 27 at 23:19
  • 7
    $\begingroup$ @Henri, "The Art of Knuth"? $\endgroup$ – Gerry Myerson Oct 28 at 4:30
  • 2
    $\begingroup$ "The art of computer programming" by Knuth, most likely. $\endgroup$ – jamesh625 Oct 31 at 22:48
22
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! I was not familiarized with Eulerian polynomials. I really enjoyed learning about this and the approach. $\endgroup$ – Francisco Oct 30 at 5:27
  • $\begingroup$ 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$. $\endgroup$ – Fedor Petrov Oct 30 at 7:45
  • $\begingroup$ 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. $\endgroup$ – esg Oct 30 at 16:24
16
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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