Prove that $\lim_{m\to\infty} \sum_{n=0}^{m} \frac{(-1)^n}{n!} \binom{m}{n}=0$.

The problem from the statement is the hardest part of the problem A. 810 from KöMaL contest November 2021 (the deadline was 10 December). After the deadline, I noticed that if $r_0=1$: $$\begin{align} \sum_{n=0}^m r_n&=\sum_{t=0}^m\sum_{n=t}^m\frac{(-1)^t}{(t+1)!}\binom{n}t\\&= \sum_{t=0}^m\frac{(-1)^t}{(t+1)!}\sum_{n=t}^m \binom{n}{t}\\&=\sum_{t=0}^m\frac{(-1)^t}{(t+1)!}\binom{m+1}{t+1}. \end{align} $$ Therefore the KöMaL problem is equivalent to $$\begin{align} &\lim_{m\to\infty}\sum_{n=0}^m r_n=1\Leftrightarrow\\&\lim_{m\to\infty}\sum_{t=0}^m\frac{(-1)^t}{(t+1)!}\binom{m+1}{t+1}=1\Leftrightarrow\\ &\lim_{n\to\infty}\sum_{t=1}^{m+1}\frac{(-1)^t}{t!}\binom{m+1}t=-1 \end{align} $$ which equivalent to

$\displaystyle \lim_{m\to\infty} \sum_{n=0}^{m} \frac{(-1)^n}{n!} \binom{m}{n} = 0$

and I cannot prove this affirmation.

My ideas:

1. To study the function $f_m:\mathbb{R}\to\mathbb{R},$ $f_m(x)=\sum\limits_{n=0}^m (-1)^n\binom{m}{n}\frac{x^{n}}{n!}$.
2. To use Cauchy product of two series.

Solution 1:

Let $I_m=\sum\limits_{n=0}^m \dfrac{(-1)^n}{n!}\dbinom{m}{n}$ and notice that $$\frac{1}{2\pi} \int_{-\pi}^{\pi} e^{-nit} e^{e^{it}} dt = \frac{1}{n!} \tag{1}$$

This is easily proven by using the power series of the exponential and writing $$e^{e^{it}}=\sum_{k\geq 0} \frac{e^{ikt}}{k!}\tag{2}$$ and exchanging sum and integral. Then you notice that all terms but the one for $k=n$ are zero.

With $(1)$, you can then write

$$\begin{split} I_m&=\frac 1 {2\pi}\sum\limits_{n=0}^m (-1)^n\dbinom{m}{n}\int_{-\pi}^{\pi} e^{-nit} e^{e^{it}} dt\\ &= \frac 1 {2\pi}\int_{-\pi}^{\pi} \sum\limits_{n=0}^m (-1)^n\dbinom{m}{n}e^{-nit} e^{e^{it}} dt\\ &= \frac 1 {2\pi}\int_{-\pi}^{\pi} \left(1-e^{-it}\right)^m e^{e^{it}} dt \end{split}$$ With this, inspired by @Gary to sum all the $I_m$'s $$\sum_{m=0}^{+\infty} I_m=\frac 1 {2\pi}\int_{-\pi}^\pi \left(\sum_{m=0}^{+\infty} \left(1-e^{-it}\right)^m\right) e^{e^{it}} dt = \frac 1 {2\pi}\int_{-\pi}^\pi e^{it} e^{e^{it}} dt=0$$ where again, we get $0$ because you can use $(2)$ and observe that all terms of the series are non-constant (integer) powers of the complex exponential, which all integrate to $0$ over $(-\pi, \pi)$.

Thus $$\boxed{\lim_{m\rightarrow+\infty}I_m= 0}$$

Additional notes: My previous answer also showed that the following recurrence formula holds:

$$(m+1)I_{m+1}-2mI_m+mI_{m-1}=0$$ which can be useful for fast numerical computation of the $I_m$'s (each is computed in $\mathcal O(1)$ steps instead of $\mathcal O(m)$ with the original formula).

And if you consider the generating function $f(z)=\sum_{m\geq 0}I_m z^m$, the recurrence relation above proves that $(z-1)^2f^\prime(z)+zf(z)=0$, which implies that $f(z)=\frac{C}{1-z}e^{\frac 1 {z-1}}$ with $C=f(0)e=e$.

Solution 2:

New Answer. Let $I_n = \sum_{k=0}^{n} \frac{(-1)^k}{k!} \binom{n}{k}$ be the sum in OP, and let $f(z) = \sum_{n=0}^{\infty} I_n(x) z^n$ be the generating function of $(I_n)$. Then by Fubini's theorem¹⁾, for $|z| < 1$,

\begin{align*} f(z) &= \sum_{n=0}^{\infty} \sum_{k=0}^{n} \frac{(-1)^k}{k!^2} n(n-1)\cdots(n-k+1) z^n \\ &= \sum_{k=0}^{\infty} \frac{(-1)^k}{k!^2} \sum_{n=k}^{\infty} n(n-1)\cdots(n-k+1) z^n \\ &= \sum_{k=0}^{\infty} \frac{(-1)^k}{k!} \frac{z^k}{(1-z)^{k+1}} \\ &= \frac{1}{1-z} e^{-\frac{z}{1-z}} = \frac{e}{1-z} e^{-\frac{1}{1-z}}. \end{align*}

On the other hand, starting from the above formula and using Fubini's theorem²⁾ again,

\begin{align*} f(z) &= e \sum_{k=0}^{\infty} \frac{(-1)^k}{k!} \frac{1}{(1-z)^{k+1}} \\ &= e \sum_{k=0}^{\infty} \frac{(-1)^k}{(k!)^2} \int_{0}^{\infty} t^k e^{-(1-z)t} \, \mathrm{d}t \\ &= e \int_{0}^{\infty} e^{-(1-z)t} \biggl( \sum_{k=0}^{\infty} \frac{(-1)^k}{(k!)^2} t^k \biggr) \, \mathrm{d}t \\ &= e \int_{0}^{\infty} e^{zt} e^{-t} J_0(2\sqrt{t}) \, \mathrm{d}t \\ &= \sum_{n=0}^{\infty} \biggl( e \int_{0}^{\infty} \frac{t^n e^{-t}}{n!} J_0(2\sqrt{t}) \, \mathrm{d}t \biggr) z^n, \end{align*}

where $J_0(\cdot)$ is the Bessel function of the first kind of order $0$. This shows that

$$ I_n = e \int_{0}^{\infty} \frac{t^n e^{-t}}{n!} J_0(2\sqrt{t}) \, \mathrm{d}t. $$

Now the desired claim follows from $\lim_{x\to\infty} J_0(x) = 0$ and the next lemma:

Lemma. Let $g : [0, \infty) \to \mathbb{C}$ be continuous and satisfies $\lim_{x\to\infty} g(x) = 0$. Then $$ \lim_{n\to\infty} \int_{0}^{\infty} \frac{t^n e^{-t}}{n!} g(t) \, \mathrm{d}t = 0. $$

Note that this is an instance of the Abelian theorems, which roughly tells that the limit of "averaged function" is the same as the limit of the original function.

Proof of Lemma. It is clear that $g$ is bounded on $[0, \infty)$. Let $M$ be a bound of $g$. Also, for any $\varepsilon > 0$, fix $R > 0$ such that $|g(x)| < \varepsilon$ whenever $x \geq R$. Then

\begin{align*} \left| \int_{0}^{\infty} \frac{t^n e^{-t}}{n!} g(t) \, \mathrm{d}t \right| \leq \int_{0}^{R} \frac{t^n e^{-t}}{n!} |g(t)| \, \mathrm{d}t + \varepsilon \int_{R}^{\infty} \frac{t^n e^{-t}}{n!} \, \mathrm{d}t \leq \frac{R^n e^{-R}}{n!} M + \varepsilon. \end{align*}

So by letting $\limsup$ as $n\to\infty$,

$$ \limsup_{n\to\infty} \left| \int_{0}^{\infty} \frac{t^n e^{-t}}{n!} g(t) \, \mathrm{d}t \right| \leq \varepsilon. $$

Since $\varepsilon > 0$ is arbitrary, the desired conclusion follows. $\square$

^{1) Here, Fubini's theorem is applicable because $$ \sum_{k=0}^{\infty} \left| \frac{(-1)^k}{k!^2} \sum_{n=k}^{\infty} n(n-1)\cdots(n-k+1) z^n \right| \leq \sum_{k=0}^{\infty} \frac{1}{k!} \frac{|z|^k}{(1-|z|)^{k+1}} < \infty. $$}

^{2) Here, Fubini's theorem is applicable because $$ \sum_{k=0}^{\infty} \int_{0}^{\infty} \left| \frac{(-1)^k}{(k!)^2} \cdot t^k e^{-(1-z)t} \right| \, \mathrm{d}t \leq \sum_{k=0}^{\infty} \frac{1}{(k!)^2} \int_{0}^{\infty} t^k e^{-(1-\operatorname{Re}z)t} \, \mathrm{d}t = \sum_{k=0}^{\infty} \frac{1}{k!} \frac{1}{(1-\operatorname{Re}z)^{k+1}} < \infty. $$ and $$ \int_{0}^{\infty} \sum_{n=0}^{\infty} \left| \frac{(zt)^n e^{-t}}{n!} J_0(2\sqrt{t}) \right| \, \mathrm{d}t \leq \Bigl( \sup |J_0| \Bigr) \int_{0}^{\infty} e^{|z|t}e^{-t} \, \mathrm{d}t < \infty. $$}

Old Answer. Let $I_m := \sum_{n=0}^{m} \frac{(-1)^n}{n!} \binom{m}{n}$. Then the generating function of $(I_m)$ is given by

$$ f(z) = \frac{1}{1-z} e^{1 + \frac{1}{z-1}} $$

for $|z| < 1$, confirming @Stefan Lafon's observation independently. From this,

$$ I_n = \frac{1}{2\pi i} \int_{|z| = 0^+} \frac{f(z)}{z^{n+1}} \, \mathrm{d}z \qquad \biggl(= \frac{1}{2\pi i} \int_{|z| = r} \frac{f(z)}{z^{n+1}} \, \mathrm{d}z \quad \text{for any } 0 < r \ll 1 \biggr) $$

However, since $f(z)$ is analytic near $\infty$, we may think of the above contour integral as the negative of the contour integral enclosing the "exterior" of $|z| =r$. Then by the residue theorem, it follows that

\begin{align*} I_n = -\mathop{\underset{z=1}{\mathrm{Res}}} \frac{f(z)}{z^{n+1}} \stackrel{(w=z-1)}= -\mathop{\underset{w=0}{\mathrm{Res}}} \frac{f(w+1)}{(w+1)^{n+1}} = \frac{1}{2\pi i} \int_{|w| = 0^+} \frac{e^{1 + \frac{1}{w}} }{w (w+1)^{n+1}} \, \mathrm{d}w \end{align*}

Now by invoking the formula

$$ \frac{n!}{s^{n+1}} = \int_{0}^{\infty} t^n e^{-st} \, \mathrm{d}t, \tag{$\operatorname{Re}(s) > 0$} $$

it follows that

\begin{align*} I_n &= \frac{1}{2\pi i} \int_{|w| = 0^+} \frac{e^{1 + \frac{1}{w}} }{w} \biggl( \frac{1}{n!} \int_{0}^{\infty} t^n e^{-(w+1)t} \, \mathrm{d}t \biggr) \, \mathrm{d}w \\ &= e \int_{0}^{\infty} \frac{t^n e^{-t}}{n!} \biggl( \frac{1}{2\pi i} \int_{|w| = 0^+} \frac{e^{\frac{1}{w} - tw} }{w} \, \mathrm{d}w \biggr) \, \mathrm{d}t \\ &= e \int_{0}^{\infty} \frac{t^n e^{-t}}{n!} \biggl( \frac{1}{2\pi i} \int_{|w| = 0^+} \frac{e^{-\sqrt{t}(\xi - \xi^{-1})} }{\xi} \, \mathrm{d}\xi \biggr) \, \mathrm{d}t \tag{$w\mapsto \xi/\sqrt{t}$} \\ &= e \int_{0}^{\infty} \frac{t^n e^{-t}}{n!} J_0(2\sqrt{t}) \, \mathrm{d}t. \tag{*} \end{align*}

where we utilized the generating function of $J_{\nu}$'s to evaluate the inner residue in the last step.

Now, considering that the function $t \mapsto t^ne^{-t}/n!$ is concentrated near $t = n$, $\text{(*)}$ suggests that $I_n$ is asymptotically $e J_0(2\sqrt{n})$, confirming @Gary's observation $I_n \asymp J_0(2\sqrt{n})$ in the now-deleted answer.

Now we justify this heuristics and conclude the proof.

Proof 1. - Hard analysis. Since $J_0$ is bounded, we may bound $|I_n|$ by

\begin{align*} |I_n| &\leq e \biggl( \sup_{[0,\infty)} |J_0| \biggr) \int_{0}^{n/2} \frac{t^n e^{-t}}{n!} \, \mathrm{d}t + e \biggl( \sup_{[\sqrt{2n},\infty)} |J_0| \biggr) \int_{n/2}^{\infty} \frac{t^n e^{-t}}{n!} \, \mathrm{d}t. \end{align*}

Since $t \mapsto t^n e^{-t}$ is increasing for $t \in [0, n]$, we can further bound this by

\begin{align*} |I_n| &\leq e \biggl( \sup_{[0,\infty)} |J_0| \biggr) \int_{0}^{n/2} \frac{(n/2)^n e^{-n/2}}{n!} \, \mathrm{d}t + e \biggl( \sup_{[\sqrt{2n},\infty)} |J_0| \biggr) \int_{0}^{\infty} \frac{t^n e^{-t}}{n!} \, \mathrm{d}t \\ &= e \biggl( \sup_{[0,\infty)} |J_0| \biggr) \frac{(n/2)^{n+1}e^{-n/2}}{n!} + e \biggl( \sup_{[\sqrt{2n},\infty)} |J_0| \biggr). \end{align*}

However, since $J_0(x) \to 0$ as $x \to \infty$ and $n! \sim \sqrt{2\pi} \, n^{n+\frac{1}{2}}e^{-n}$ as $n\to\infty$, it follows that the above bound converges to $0$:

$$ \frac{(n/2)^{n+1}e^{-n/2}}{n!} \sim \frac{\sqrt{n}}{2\sqrt{2\pi}} \cdot \frac{e^{n/2}}{2^n} \xrightarrow{n\to\infty} 0 $$

and

$$ \lim_{n\to\infty} \sup_{[\sqrt{2n},\infty)} |J_0| = \limsup_{x\to\infty} |J_0(x)| = 0. $$

Therefore $I_n$ converges to $0$ as $n\to\infty$.

Proof 2. - Using probability theory. Let $T_1, T_2, \ldots$ be i.i.d. $\operatorname{Exp}(1)$ variables. Using this, $\text{(*)}$ can be recast as

$$ I_n = e \mathbf{E}[J_0(2\sqrt{T_1 + T_2 + \cdots + T_{n+1}})]. $$

However, by an application of SLLN, we find that $T_1 + \cdots + T_{n+1} \to \infty$ almost surely. Therefore by the bounded convergence theorem,

$$ \lim_{n\to\infty} I_n = e \mathbf{E}\Bigl[ \lim_{n\to\infty} J_0(2\sqrt{T_1 + T_2 + \cdots + T_{n+1}}) \Bigr] = 0. $$

Solution 3:

According to Wikipedia the Laguerre polynomials can be defined as

$$L_m (x)=\sum_{n=0}^{m} \frac{(-1)^n}{n!} x^n$$

Hence the sum of the OP is just $L_m(1)$.

The leading term of the asymptotic behaviour for large $m$ is

$$L_m (1)\simeq\sqrt{\frac{e}{\pi }} \sqrt[4]{\frac{1}{m}} \cos \left(2 \sqrt{m}-\frac{\pi }{4}\right)$$

Hence $\lim_{m\to \infty}L_m(1)=0$.

Solution 4:

Unfortunately the posed problem is much more difficult. So here my solution.

The given formula can be identified as

$LaguerreL(m,1)$.

In words this is the formula of a Laguerre L polynomial for degree $m$ evaluated at the point $x=1$!

$LaguerreL(m,1)=\sum_{m=0}^{n}\frac{(-1)^n}{n!}\binom{m}{n}$

as required. This identity can be easily verified over at Wolfram Alpha Pro.

This is already a short notation for $L^{0}_{m}(1)=L(m,0,1)$.

Let us calculate some values to get an idea of what is going on:

m value of the alternating sum 0. 1 5000 -0.0823773 10000 -0.0250789 15000 0.0536988 20000 0.0606476

So this is neither only negative or positive. For smaller $m$ is has periods of increase and decrease. That is really confusing for the proposal of behavior for very large values.

For m a million this is still not smaller. It is 0.0116919.

So discreteness is contraproductive for making an impression.

Better is a plot:

From this plot follows that is should be possible to Fourier transform the series and look at the Fourier transform for the behaviour for large m.

The problem is for very small m the function does not behave nice.

Now take the comparable function that has already been mentioned in a different context of this question answers and look:

With this graphical or visual prove it gets clear what Dr. Wolfgang-Hintze intended but did not prove or even answer.

From very small values of m to very large the compare cosine is very close to the series under treatment. We are allowed with this match to replace our numerical experiments with the functions values of the trigonometric approximation.

It follows for every $m$ the approixmation is close to the numerial result for the series even for very large $m$. This is consequence of the attribute that trigonometric function are a complete space for approximations see for example the Fourier Approximation theory.

$\lim_{m\rightarrow\infty}L(m,0,1)=\lim_{m\rightarrow\infty}\frac{cos(\sqrt{m}-\frac{\pi}{4})}{m^{\frac{1}{4}}}=0$

The limit is done over the Laguerre polynoms index in the first component.

The approximation is true for positive and negative values of the series over m and the series sequence converges absolute like the the negative power of one quarter of m to zero.

There is no need to calculate the amplitude since this is close to one. But the phase $\frac{\pi}{4}$ is needed very much because otherwise the cosine would be shifted along the $m$ - axis and this destroys the great visual impression. The frequency is then a big problem. This is not very Fourier but a easy guess after the decision for approximation is made. For proving the identity on $\mathbb R$ in the Fourier approximation theory it is only needed that the approximated function is approxed in a finite intervall as is shown in the graph. The graphs several periods not only one.

The graph too confirms the rather slow convergence to zero.

I think this is a prove and convinces the last one.