# Why can you place in the recursive definition to find the limit?

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?

• 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. – eranreches Apr 3 '15 at 15:01
• What do you mean by placement? – Tim Raczkowski Apr 3 '15 at 15:09
• 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$. – 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.

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