# Proving limit of the recursive sequence $x_{n+1} = x_n - \ln(x_n)$

I have the following sequence: $x_{n+1} = x_n - \ln(x_n)$ where $x_0 = 2$.

The question is: Proof whether $x_n$ converges, and if it does; determine the limit. What I have done so far:

1. Proof $x_n$ converges:

$$\frac{x_{n+1}}{x_n} = \frac{x_n - \ln(x_n)}{x_n} < 1 \ \forall_{n \in \mathbb{N}}$$

Thus $x_n$ is strictly decreasing.

We show: $x_n \geq 1$ by induction.

$x_0 = 2 > 1$ (base case). Suppose $x_n \geq 1$ for all $n \in \mathbb{N}$. Then for $x_{n+1}$:

$x_n \geq 1 \Rightarrow \ln(x_n) \geq 0 \Rightarrow x_{n+1} = x_n - \ln(x_n) \geq 1$

Since the sequence is strictly decreasing and bounded below by 1, the sequence converges. $\blacksquare$

2. If I show $1 + \epsilon$ is not a greater lower bound for the sequence for all $\epsilon > 0$ then I can conclude $x_n \rightarrow 1$ as $n \rightarrow \infty$.

My thought was; suppose $\exists_{\epsilon > 0} : x_n \geq 1 + \epsilon$

This should lead to a contradiction, right?

• You suddenly changed from $x_n-\ln(x_n)$ to $x_n+\ln(x_n)$ in your point 1. – Bananach Jan 28 '16 at 12:42
• Continued: The statment of 1. is correct nevertheless. What is the problem in executing 2? – Bananach Jan 28 '16 at 12:46
• @Bananach Thank you, I fixed it ;) Although I'm not sure if it still holds now..? – Dennis van den Berg Jan 28 '16 at 12:47
• It does hold, by concavity of $\ln$ (details left to you). Also to step 2: Note that if $x_n\geq 1+\varepsilon$, then $ln(x_n)\geq ln(1+\varepsilon)>0$ (monotonicity of $\ln$) which shows that your sequence makes steps whose length is bounded below, i.e. it converges to minus infinity which contradicts your point 1. – Bananach Jan 28 '16 at 12:48
• For future similar problems, a little help to figure out the limit non-rigorously. If $x_n$ converges to $x$, then for large $n$ approximately $x_{n+1}=x_n=x$. Inserting this into the recurrence formula gives you an equation that the limit satisfies. In your example this equation is simply $\ln(x)=0$. – Bananach Jan 28 '16 at 12:51

## 2 Answers

First of all your proof that $x_{n+1}\ge 1$ has an issue. If you assume that $x_n\ge1$ you I agree that you have that $\ln x_n\ge0$, but how does that imply that $x_n-\ln x_n\ge 1$? What you need to use is an upper estimate of $\ln x_n$ namely that $\ln x_n \le x_n-1$.

Now for the convergence, we can use the fact that the convergence of a recursion of the form $x_{n+1} = \phi(x_n)$ must be to a fixpoint of $\phi$. This implies that the limit fulfills the equation $x = x - \ln x$ which means that $x=1$.

To show that it has to be a fixpoint we use that $x_{n+1}-x_{n} = \phi(x_n)-x_n$ converges to zero. And since $\phi(x_n)-x_n$ is continuous we have that $\lim \phi(x_n)-x_n = \phi(\lim x_n) - \lim x_n$.

Thanks to @Bananach for helping me out.

Since $x_n$ converges (to, say; $L$), for large $n$; $x_{n+1} = x_n = L$.

But then $L = L - ln(L) \Rightarrow ln(L) = 0 \Rightarrow L = 1$. $\blacksquare$

• However, as Bananach said, this technique is not rigorous. And if the sequence isn't well-behaved (or doesn't converge) it can give crazy answers. So while it can be helpful, you still need to do the stuff with bounds. – PM 2Ring Jan 28 '16 at 13:02
• It's not correct to write "for large $n$; $x_{n+1} = x_n = L$". You could write $x_{n+1}\approx x_n \approx L$. You could also say that since $(x_n)$ converges, we have $x_n - x_{n+1} \to 0$. But that is, here, $\ln x_n \to 0$, which in turn is equivalent to $x_n \to 1$. – Daniel Fischer Jan 28 '16 at 13:02