Let $\{a_n\}_{n\in\mathbb{N}}$ be a sequence of real numbers such that:

$$\forall n\in\mathbb{N},\quad a_{n+1}=a_n + e^{-a_n}.$$

Prove that:

$$\lim_{n\to+\infty}\frac{a_n}{\log n}=1.$$

  • 1
    $\begingroup$ Welcome to math.SE! Can you share what you've tried, and explain what you're having trouble with? Do you know any related results that might be useful here? $\endgroup$ – user61527 Jul 27 '14 at 3:17
  • $\begingroup$ This is very similar to 2012 Putnam Problem B4 artofproblemsolving.com/Forum/… $\endgroup$ – JimmyK4542 Jul 27 '14 at 3:17

As I stated, this is similar to 2012 Putnam Exam Problem B4 which asks to prove a stronger statement. Here is a more detailed version of one of the solutions in that AoPS thread:

Clearly, $a_{n+1}-a_n = e^{-a_n} > 0$, so $\{a_n\}_{n = 1}^{\infty}$ is strictly increasing.

Hence, either $\displaystyle\lim_{n \to \infty}a_n = L$ (a finite number) or $\displaystyle\lim_{n \to \infty}a_n = \infty$. Suppose $\displaystyle\lim_{n \to \infty}a_n = L$.

Then, $L = \displaystyle\lim_{n \to \infty}a_{n+1} = \lim_{n \to \infty}a_n+e^{-a_n} = L+e^{-L}$, i.e. $e^{-L} = 0$, a contradiction. So, $\displaystyle\lim_{n \to \infty}a_n = \infty$.

Now consider $\displaystyle\lim_{n \to \infty}\dfrac{e^{a_n}}{n}$. By Cesaro-Stolz, this limit is equal to $\displaystyle\lim_{n \to \infty}\dfrac{e^{a_{n+1}}-e^{a_n}}{(n+1)-n}$ (iff both exist).

$\displaystyle\lim_{n \to \infty}\dfrac{e^{a_{n+1}}-e^{a_n}}{(n+1)-n} = \lim_{n \to \infty}e^{a_{n+1}}-e^{a_n} = \lim_{n \to \infty}\dfrac{e^{a_{n+1}-a_{n}}-1}{e^{-a_n}} = \lim_{n \to \infty}\dfrac{e^{e^{-a_n}}-1}{e^{-a_n}} = \lim_{x \to 0}\dfrac{e^x-1}{x} = 1$.

Thus, $\displaystyle\lim_{n \to \infty}\dfrac{e^{a_n}}{n} = 1$. Taking the natural log yields $\displaystyle\lim_{n \to \infty}(a_n - \ln n) = 0$.

Then, since $\displaystyle\lim_{n \to \infty}\ln n = \infty$, we have $\displaystyle\lim_{n \to \infty}\dfrac{a_n}{\ln n} = \lim_{n \to \infty}\left[\dfrac{a_n - \ln n}{\ln n}+1\right] = 1$.


Since $f(x)=x+e^{-x}$ has the only stationary point $x=0$ we have $f(x)\geq f(0)=1$, hence $a_1=s\geq 1$. Since $e^{-x}\geq 0$, the sequence is increasing. Since $f'(x)\geq 0$ on $\mathbb{R}^+$, for any $n\geq 1$ $a_n\geq h$ implies $a_{n+1}\geq f(h)$ and $a_n\leq h$ implies $a_{n+1}\leq f(h)$. Since the sequence is increasing, the increment $a_{n+1}-a_n = e^{-a_n}$ is decreasing, hence the sequence is concave.

If we had the continuous problem $$ g'(x) = e^{-g(x)} $$ to state that $g(x)\sim\log x$ it would be sufficient to multiply both sides by $e^{g(x)}$ and integrate between $0$ and $y$ to have: $$ e^{g(y)}-e^{g(0)} = y,$$ from which $g(x) = \log\left(y+e^{g(0)}\right)$. Let us try to do the same here, with the discrete analogue.

We have: $$ (a_{n+1}-a_n) e^{a_n} = 1,$$ hence by summing both sides with $n$ that runs from $1$ to $N$ we have: $$ N = \sum_{n=1}^{N}\left(a_{n+1}-a_n\right) e^{a_n},$$ but since $e^x$ is a convex function $$ (a_{n+1}-a_{n}) e^{a_{n}}\leq e^{a_{n+1}}-e^{a_n} \leq (a_{n+1}-a_{n}) e^{a_{n+1}} $$ holds, hence: $$ N \leq \sum_{n=1}^{N}\left(e^{a_{n+1}}-e^{a_n}\right) = e^{a_{N+1}}-e^{a_1}, $$ so: $$ a_{N}\geq \log(N-1+e^{a_1}),\tag{1} $$ while, due to the concavity of the sequence: $$ N \geq \sum_{n=1}^{N}\left(e^{a_{n+1}}-e^{a_n}\right)e^{a_{n}-a_{n+1}} \geq e^{a_1-a_2}\cdot\left(e^{a_{N+1}}-e^{a_1}\right),$$ so: $$ a_N\leq\log(e^{a_2-a_1}(N-1)+e^{a_1})\tag{2}$$ and $$\lim_{N\to+\infty}\frac{a_N}{\log N}=1$$ follows by squeezing. With the same approach (by summing between $N$ and $2N-1$) we can also prove the stronger statement: $$\lim_{N\to +\infty}(a_N-\log N) = 0.$$


$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ \begin{align} &\mbox{Heuristically}\quad \totald{a_{n}}{n} + a_{n}\sim a_{n} + \expo{-a_{n}} \quad\imp\quad\expo{a_{n}}\sim n + \mbox{constant} \\[3mm]&\imp\quad{\ln\pars{a_{n}} \over \ln\pars{n}} ={\ln\pars{n + \mbox{constant}} \over \ln\pars{n}} \stackrel{n \to \infty}{{\LARGE \to}} 1 \end{align}


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.