[Soln] 2016 Putnam Problem B1

2016 Putnam B1. Let $x_0, x_1, x_2, \dots$ be the sequence such that $x_0 = 1$ and for $n \geq 0$, $x_{n+1} = \ln(e^{x_n} - x_n)$ (as usual, the function $\ln$ is the natural logarithm.

Show that the infinite series $x_0 + x_1 + x_2 + \dots$ converges and find its sum.

The recurrence relation is begging to be exponentiated so that we have $e^{\text{something}}$ on both sides:

\begin{aligned} e^{x_{n+1}} &= e^{x_n} - x_n, \\ x_n &= e^{x_n} - e^{x_{n+1}}, \end{aligned}

and now this looks like a telescoping series that allows cancellation of terms:

\begin{aligned} x_0 + x_1 + \dots + x_n &= \sum_{i = 0}^n e^{x_i} - e^{x_{i+1}} \\ &= e^{x_0} - e^{x_{n+1}} \\ &= e - e^{x_{n+1}}. \end{aligned}

To show that $x_0 + x_1 + x_2 + \dots$ converges, we have to show that $\lim_{n \rightarrow \infty} x_n$ exists. There are many different techniques to show that a limit exists, we can decide which is appropriate by playing around with the sequence.

After working out the first few terms of the sequence, it may become clear that the sequence is decreasing. The recurrence relation seems to suggest it as well: if we can state with confidence that $x_n$ is non-negative, then

\begin{aligned} e^{x_{n+1}} &= e^{x_n} - x_n \leq e^{x_n}, \\ x_{n+1} &\leq x_n. \end{aligned}

It seems reasonable that $x_n$ should be positive as well. Let’s try using induction to prove both statements at once:

Induction statement $P_n$: For $n \geq 0$, $x_n \geq 0$ and $x_n \geq x_{n+1}$.

It is clear that $P_0$ is true. Let us assume that $P_n$ is true for some $n \geq 0$. To prove $x_{n+1} \geq 0$, we can work backwards:

\begin{aligned} &&&x_{n+1} &&\geq 0 \\ &\Leftrightarrow &&\ln(e^{x_n} - x_n) &&\geq 0 \\ &\Leftrightarrow &&e^{x_n} - x_n &&\geq 1 \\ &\Leftrightarrow &&e^{x_n} &&\geq 1 + x_n, \end{aligned}

which is a true statement for all real numbers $x_n$! Hence the sequence is non-negative and we can use the earlier argument to show that $x_{n+1} \leq x_n$. We have shown that $P_n \Rightarrow P_{n+1}$, so by induction, the induction statement is true.

Since we have a decreasing sequence with a fixed lower bound, it means that the sequence converges. It remains to figure out what the limit $L = \lim_{n \rightarrow \infty} x_n$ is. We can use the recurrence relation to figure that out:

\begin{aligned} L &=\lim_{n \rightarrow \infty} e^{x_n} - e^{x_{n+1}} \\ &= e^{\lim x_n} - e^{\lim x_{n+1}} \\ &= e^L - e^L \\ & = 0. \end{aligned}

Hence, $\lim_{n \rightarrow \infty} x_n = 0$, and

$\lim \sum_{i = 0}^\infty x_i = \lim (e - e^{x_i}) = e - e^0 = \boxed{e-1}.$

Done!