Putnam 2012, Problem B-4

Suppose that $a_0 = 1$ and that $a_{n+1} = a_n + e^{-a_n}$ for $n = 0, 1, 2, \ldots$. Does $a_n - \log n$ have a finite limit as $n \to \infty$? (Here $\log n = \log_e n = \ln n$.)

Solution:
**First solution.** We will show that the answer is yes. First note that for all $x > -1$, $e^x \geq 1+x$ and thus
$$x \geq \log(1+x). \tag{2}$$

We next claim that $a_n > \log(n+1)$ (and in particular that $a_n - \log n > 0$) for all $n$, by induction on $n$. For $n = 0$ this follows from $a_0 = 1$. Now suppose that $a_n > \log(n+1)$, and define $f(x) = x + e^{-x}$, which is an increasing function in $x > 0$; then
$$a_{n+1} = f(a_n) > f(\log(n+1))$$
$$= \log(n+1) + 1/(n+1) \geq \log(n+2),$$
where the last inequality is (2) with $x = 1/(n+1)$. This completes the induction step.

It follows that $a_n - \log n$ is a decreasing function in $n$: we have
$$(a_{n+1} - \log(n+1)) - (a_n - \log n)$$
$$= e^{-a_n} + \log(n/(n+1))$$
$$< 1/(n+1) + \log(n/(n+1)) \leq 0,$$
where the final inequality is (2) with $x = -1/(n+1)$. Thus $\{a_n - \log n\}_{n=0}^{\infty}$ is a decreasing sequence of positive numbers, and so it has a limit as $n \to \infty$.

**Second solution.** Put $b_n = e^{a_n}$, so that $b_{n+1} = b_n e^{1/b_n}$. In terms of the $b_n$, the problem is to prove that $b_n/n$ has a limit as $n \to \infty$; we will show that the limit is in fact equal to $1$.

Expanding $e^{1/b_n}$ as a Taylor series in $1/b_n$, we have
$$b_{n+1} = b_n + 1 + R_n$$
where $0 \leq R_n \leq c/b_n$ for some absolute constant $c > 0$. By writing
$$b_n = n + e + \sum_{i=0}^{n-1} R_i,$$
we see first that $b_n \geq n + e$. We then see that
$$0 \leq \frac{b_n}{n} - 1$$
$$\leq \frac{e}{n} + \sum_{i=0}^{n-1} \frac{R_i}{n}$$
$$\leq \frac{e}{n} + \sum_{i=0}^{n-1} \frac{c}{nb_i}$$
$$\leq \frac{e}{n} + \frac{c \log n}{n}.$$

It follows that $b_n/n \to 1$ as $n \to \infty$.

**Remark.** This problem is an example of the general principle that one can often predict the asymptotic behavior of a recursive sequence by studying solutions of a sufficiently similar-looking differential equation. In this case, we start with the equation $a_{n+1} - a_n = e^{-a_n}$, then replace $a_n$ with a function $y(x)$ and replace the difference $a_{n+1} - a_n$ with the derivative $y'(x)$ to obtain the differential equation $y' = e^{-y}$, which indeed has the solution $y = \log x$.