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?

  • $\begingroup$ You suddenly changed from $x_n-\ln(x_n)$ to $x_n+\ln(x_n)$ in your point 1. $\endgroup$ – Bananach Jan 28 '16 at 12:42
  • $\begingroup$ Continued: The statment of 1. is correct nevertheless. What is the problem in executing 2? $\endgroup$ – Bananach Jan 28 '16 at 12:46
  • $\begingroup$ @Bananach Thank you, I fixed it ;) Although I'm not sure if it still holds now..? $\endgroup$ – Dennis van den Berg Jan 28 '16 at 12:47
  • $\begingroup$ 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. $\endgroup$ – Bananach Jan 28 '16 at 12:48
  • 1
    $\begingroup$ 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$. $\endgroup$ – Bananach Jan 28 '16 at 12:51

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$

  • $\begingroup$ 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. $\endgroup$ – PM 2Ring Jan 28 '16 at 13:02
  • 1
    $\begingroup$ 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$. $\endgroup$ – Daniel Fischer Jan 28 '16 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.