When required to find limits of recursive sequences, i.e. $$x_{n+1}=\frac{1}{4-x_n}\qquad x_0=3$$

The steps are usually pretty consistent. First you prove it's monotonous and bounded, and therefore converges, then you place $L$ in the equation and compute the limit itself.

$$L=\frac{1}{4-L}\implies L=1\pm \frac{\sqrt{3}}{2}$$

And then you choose the lower one because it's the real limit.

Now the placement seems to be a recurring motive, but I just can't understand why it's true, especially since you get 2 "limits" where one of them is just magically right.

The only explanation I seem to find is that $x_{n+1}$ and $x_n$ are actually the same sequence, which I sort of intuitively understand, but I'm still uncertain of. Is there any rigorous justification for this placement?

  • $\begingroup$ You can formly prove that $ a_{n} $ and $ a_{n+1} $ have the same limit. Just use the $\varepsilon - \delta $ definition of the limit and take the $ N $ whice suits the problem. $\endgroup$ – eranreches Apr 3 '15 at 15:01
  • $\begingroup$ What do you mean by placement? $\endgroup$ – Tim Raczkowski Apr 3 '15 at 15:09
  • 1
    $\begingroup$ The function defining the recursion must be continuous, otherwise you can't determine the limit in that way. If $f$ is continuous and $(y_n)$ is defined via a starting value and the recursion $y_{n+1} = f(y_n)$, then from $\lim f(y_n) = f(\lim y_n)$ you obtain that the limit must be a fixed point of $f$. $\endgroup$ – Daniel Fischer Apr 3 '15 at 15:17

The reason we can replace $x_n$ and $x_{n+1}$ with the same $L$ is because they have the same limit. To see why this is true we need the definition of the limit of a sequence: we say $x_n \to L$ when for all $\epsilon > 0$ there exists $N \in \mathbb{N}$ such that for all $n\ge N$ we have $$ |x_n - L| < \epsilon.$$

Since you have proved that $x_n$ converges we can use this definition to show that $x_{n+1}$ also converges, and to the same limit. Let $\epsilon > 0$. Let's say $x_n$ converges to some real number $L$. Then by the definition of the limit we can choose $N\in \mathbb{N}$ such that if $n\ge N$ then $|x_n - L| < \epsilon$. Now given $n\ge N$ we have $n+1 > n \ge N$ so that $$ |x_{n+1} - L| < \epsilon. $$ Thus, by the definition of the limit, $x_{n+1} \to L$.

Now that we have established that $x_{n+1}$ and $x_n$ have the same limit $L$ we can compute the limit of the recursion. Taking the limit of both sides,

$$ \lim_{n\to\infty}x_{n+1} = \lim_{n\to\infty} \frac{1}{4-x_n}. $$ Now using that $x_n \to L$ and $x_{n+1} \to L$, $$ L = \frac{1}{4-L}. $$

We can expand and simpify this to get the quadratic $$ L^2 - 4L + 1 = 0 $$ which, by the quadratic formula, has roots $$ L = 2 \pm \sqrt{3}. $$

Now the reason why $L$ is "magically" $2- \sqrt{3}$ is because it's the only root that makes sense: note that $x_n$ is monotone decreasing and bounded below by $2 - \sqrt{3}$ so it converges to $2-\sqrt{3}$ by the monotone convergence theorem.

  • $\begingroup$ That makes everything clear. Thank you very much! $\endgroup$ – Nescio Apr 3 '15 at 15:30
  • $\begingroup$ and why does the limit exist? $\endgroup$ – Dr. Sonnhard Graubner Apr 3 '15 at 15:31
  • 1
    $\begingroup$ @Dr.SonnhardGraubner as the OP has said in their question, $x_n$ is bounded and monotone. $\endgroup$ – sardoj Apr 3 '15 at 15:32
  • $\begingroup$ i can't find a proof for it $\endgroup$ – Dr. Sonnhard Graubner Apr 3 '15 at 15:33
  • 1
    $\begingroup$ @Dr.SonnhardGraubner Show by induction that $0 < x_{n+1} < x_n \le 1$ for all $n\in \mathbb{N}$. $\endgroup$ – sardoj Apr 3 '15 at 15:37

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.