Limit of a recursively defined sequence 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.$$
 A: 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$.
A: 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.$$
A: $\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}
