$a_{n+1} = a_n+\int_{a_n}^{+\infty}1-\exp(-\exp(-x))dx$

Question

I have the following recursive equation: $$a_{n+1} = a_n+\int_{a_n}^{+\infty}1-\exp(-\exp(-x))dx$$ with the initial condition $a_0 = 0$.

I would like to show that there exists a sequence $b_n$ which is asymptotically equivalent to $\ln n$ as $n$ goes to infinity, such that $a_n\geq b_n$ (at least for every $n$ large enough).

I have tried several things, such as upper bounding $1-\exp(-\exp(-x))$ by $\exp(-x)$ but I have not been successful so far.

Answer 1

Let $(a_n)$ be a sequence defined by a recursion $a_{n+1} = a_n + f(a_n) =: F(a_n)$, where $f$ is a nice positive function which decays to $0$. There is a general method to study the speed of divergence of $(a_n)$: comparison with the solution of a differential equation. Here I'll get a lower bound.

We know that $e^u \leq 1+(1+e^{-1})u$ for all $u \in [-1,0]$. Putting $u=-e^{-x}$, we get $1-e^{-e^{-x}} \geq (1+e^{-1}) e^{-x}$ for all $x \geq 0$. Since $(a_n)$ is nonnegative, we get:

$$a_{n+1} \geq a_n+\int_{a_n}^{+ \infty} (1+e^{-1}) e^{-x} \ dx = a_n+(1+e^{-1}) e^{-a_n}.$$

Let $C := (1+e^{-1})$, $y_0 \geq 0$ and $y$ be the solution of the system:

$$y(0)= y_0, \quad \quad y'(t) = Ce^{-y(t)} \ \ \forall t\geq 0.$$

This function is increasing. In addition, since the function $u \mapsto Ce^{-u}$ is decreasing, the function $t \mapsto Ce^{-y(t)}$ is decreasing. Hence, for $t \in [n,n+1]$, we have $y'(t) \leq y'(n) = Ce^{-y(n)}$. Integrating over $[n,n+1]$, we get

$$y(n+1)-y(n) \leq Ce^{-y(n)}.$$

Let $G$ be the function which maps $y_0$ to $y(1)$. Then the inequality above implies that $G \leq F$. Composing these functions $n$ times, we get $G^{n} \leq F^{n}$, and then $G^n (0) \leq F^n (0)$. But $F^n(0) = a_n$ and $G^n(0) = y(n)$, where we chose $y_0=0$.

In addition, the differential equation above can be solved explicitely:

$$dy = Ce^{-y} dt,$$

$$d(e^y) = C dt,$$

$$e^{y(t)}-e^{y_0} = Ct.$$

So, for $y_0 = 0$ we have $y(t) = \ln (1+Ct)$. Putting everything together, we finally get:

$$a_n \geq y(n) = \ln (1+Cn) \sim \ln(n).$$

Answer 2

Too long for comments.

Assuming that you may enjoy special functions $$\int \big(1-\exp(-\exp(-x))\big)\,dx=x+\text{Ei}\left(-e^{-x}\right)$$ $$\int_{a_n}^\infty \big(1-\exp(-\exp(-x))\big)\,dx=\gamma-a_n-\text{Ei}\left(-e^{-a_n}\right)$$ making $$a_{n+1}=\gamma-\text{Ei}\left(-e^{-a_n}\right)$$ Since, at this point, I do not see what I could add to D. Thomine's answer, I just computed a few numbers $$\left( \begin{array}{cccc} n & a_n & \log(n) & a_n-\log(n) \\ 5 & 1.87138 & 1.60944 & 0.261946 \\ 10 & 2.45493 & 2.30259 & 0.152341 \\ 15 & 2.81763 & 2.70805 & 0.109581 \\ 20 & 3.08208 & 2.99573 & 0.086350 \\ 25 & 3.29050 & 3.21888 & 0.071620 \\ 30 & 3.46259 & 3.40120 & 0.061390 \\ 35 & 3.60919 & 3.55535 & 0.053844 \\ 40 & 3.73691 & 3.68888 & 0.048034 \\ 45 & 3.85008 & 3.80666 & 0.043413 \\ 50 & 3.95167 & 3.91202 & 0.039645 \end{array} \right)$$