[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!

Advertisements
This entry was posted in Undergraduate, USA and tagged , , , . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s