21
$\begingroup$

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.
$\endgroup$
26
  • 3
    $\begingroup$ $(1-1)^m=\sum_{n=0}^m\binom{m}{n}(-1)^n=0$ Your expression looks funny. $\endgroup$ Dec 11, 2021 at 21:15
  • 2
    $\begingroup$ If you include $n=0$ then the limit appears correct $\endgroup$
    – FShrike
    Dec 11, 2021 at 21:29
  • 3
    $\begingroup$ this one might help you math.stackexchange.com/questions/3830604/… $\endgroup$ Dec 11, 2021 at 21:47
  • 6
    $\begingroup$ These are the values of Laguerre polynomials $L_n(1)$. The generating function is $e^{-t/(1 - t)}/(1 - t)$, which has an essential pole at $t = 1$. This shows that $\lim_{n \rightarrow \infty} \sqrt[n]{|L_n(1)|} = 1$, which unfortunately is not enough to conclude. $\endgroup$
    – WhatsUp
    Dec 11, 2021 at 22:44
  • 3
    $\begingroup$ @WhatsUp $$ L_n (1) = \sqrt {\frac{e}{{\pi \sqrt n }}} \sin \left( {2\sqrt n + \frac{\pi }{4}} \right) + \mathcal{O}(n^{ - 3/4} ) $$ $\endgroup$
    – Gary
    Dec 12, 2021 at 4:41

4 Answers 4

10
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ $\imath$ is $i$ ? $\endgroup$
    – Tashi
    Dec 12, 2021 at 10:24
  • 1
    $\begingroup$ I fixed that and added a full answer to the question. $\endgroup$ Dec 12, 2021 at 17:28
  • 4
    $\begingroup$ $\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$ How do you justify the exchange of order of integral and summation here? We don't (and shouldn't) have absolute convergence here. See Failure of Fubini's theorem for non-integrable functions. $\endgroup$
    – WhatsUp
    Dec 12, 2021 at 18:53
  • 1
    $\begingroup$ Yeah I might have gone a bit fast on this one, it's not as simple as I thought. $\endgroup$ Dec 12, 2021 at 19:25
9
$\begingroup$

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 theorem1), 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 theorem2) 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. $$

$\endgroup$
7
  • 1
    $\begingroup$ +1 Nice answer! Note that your integral formula is a special case of dlmf.nist.gov/18.10.E9 and is consistent with the fact that $I_n = L_n(1)$. $\endgroup$
    – Gary
    Dec 12, 2021 at 7:55
  • 1
    $\begingroup$ @Gary Thank you for the reference! Anyway, I actually visited that page when I was scrounging around DMLF in search of some nice integral representation of $L_n(1)$, so I feel dumb that I missed that formula and ended up redoing all the calculations by myself. $\endgroup$ Dec 12, 2021 at 8:10
  • 2
    $\begingroup$ I thought about using it in an answer but it felt like cheating a little bit. So, I think it is better that you provided a derivation for it. $\endgroup$
    – Gary
    Dec 12, 2021 at 8:13
  • 2
    $\begingroup$ Is there a way to prove to the formula $I_n=e\int_0^\infty \frac{t^ne^{-t}}{n!} J_0(2\sqrt{t})\;\mathrm{d}t$ without using complex analysis? $\endgroup$
    – Tashi
    Dec 13, 2021 at 10:48
  • 2
    $\begingroup$ @user914367, I also thought about that but was only able to revisit this question now. Anyway, I came up with a new answer, motivated by the old version but not using complex analysis. $\endgroup$ Dec 13, 2021 at 18:11
1
$\begingroup$

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

$\endgroup$
1
  • 4
    $\begingroup$ The user Gary also pointed out essentially the same asymptotic formula in the comment. Considering that this is a contest problem, are you willing to provide a more self-contained solution, including the proof of the asymptotic formula? $\endgroup$ Dec 15, 2021 at 22:54
1
$\begingroup$

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:

graph of the given series over continuous m

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:

compare the approximation to the orginal function series

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .