Limit of the sequence defined by a recurrence

Question

Given a recurrence formula for an arithmetic sequence, $$U_{n} = \frac{1}{2+U_{n-1}}$$

Show that$$\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+ ...}}}} = (SomeGivenValue)$$

How can we solve questions like this?

Answer 1

The method is to make a substitution $U_n=\frac{T_n}{T_{n+1}}$ and you would get much more tangible

$$T_{n+1}^2-2T_nT_{n+1}-T_n^2=0$$

$$(T_{n+1}-T_n-\sqrt{2}T_n)(T_{n+1}-T_n+\sqrt{2}T_n)=0$$

$$T_{n+1}-T_n-\sqrt{2}T_n=0$$ $$T_{n+1}-T_n+\sqrt{2}T_n=0$$

These two you solve classically assuming $T_n=a^n$ and when you substitute and solve you have that $a_1=1-\sqrt{2}$ and $a_2=1+\sqrt{2}$ which gives

$$T_n=c(1-\sqrt{2})^n+d(1+\sqrt{2})^n$$

and the solution follows. Set initial conditions and you have the solution.

$$U_n=\frac{c(1-\sqrt{2})^n+d(1+\sqrt{2})^n}{c(1-\sqrt{2})^{n+1}+d(1+\sqrt{2})^{n+1}}$$

Now all you need to do to get to the answer of some value is to find:

$$\lim\limits_{n \to \infty}\frac{c(1-\sqrt{2})^n+d(1+\sqrt{2})^n}{c(1-\sqrt{2})^{n+1}+d(1+\sqrt{2})^{n+1}} = \sqrt{2}-1$$

Since $c$ and $d$ depend on the initial value (in your case that would be $U_0 = \frac{1}{2}$) this proves that the initial value is irrelevant.

Three years later....

A small technical glitch

We cannot have

$$ \frac{c}{d}=\left ( \frac{\sqrt{2}+1}{\sqrt{2}-1} \right )^n= \left (3+2\sqrt{2} \right)^n$$

as this would lead to $0$ appearing down the track of $U_n$ and the quotient is then invalid. This does not affect the final conclusion as for $U_0 = \frac{1}{2}$ we have

$$ \frac{c}{d}=\left ( \frac{\sqrt{2}-1}{\sqrt{2}+1} \right )^n= \left (3-2\sqrt{2} \right)^n$$

Answer 2

Solution is much easier. Solve U = 1/(2+U).

Answer 3

To properly solve this problem, first of all, why should the limit exist at all?

As per any problem solving, we start with looking at a few numbers:

First of all, the sequence itself is not well defined - we do not know where does the sequence start, or $ U_1 $, so let's just put some guess $ U_1 = -100 $ to start with, the sequence of numbers look like this.

-100
-0.010204082
0.502564103
0.399590164
0.416737831
0.413780919
0.414287806
0.414200825

If you were me, you would recognize this look suspiciously like $ \sqrt{2} - 1 $, we will see if that's true.

Putting that value into the formula and iterate again, we see something interesting

$ \frac{1}{2 + (\sqrt{2} - 1)} = \frac{1}{(\sqrt{2} + 1)} = \frac{(\sqrt{2} - 1)}{(\sqrt{2} + 1)(\sqrt{2} - 1)} = \sqrt{2} - 1 $

So if the sequence 'ever' get to this magic sink value, it will just stuck there forever.

So we have see two 'illustrations' that shows that the answer is very probably $ \sqrt{2} - 1 $.

It is a well known fact that if a sequence converge, then it converges to an unique limit.

The only thing that is unclear is whether or not this sequence converge, the pattern you are seeing here is continued fraction and continued fraction do converges, so the answer is indeed $ \sqrt{2} - 1 $

https://en.wikipedia.org/wiki/Continued_fraction

It is interesting to note that equation 10 in the Wikipedia is exactly your problem!

Answer 4

Is easy to check that for $x>\sqrt2-1$, $x>1/(2+x)>\sqrt2-1$, so $$U_{n-1} >\sqrt2-1\implies \sqrt2-1<U_n = \frac1{2+U_{n-1}} < U_{n-1}.$$ Starting from $U_1>\sqrt2-1$, this proves that the sequence is decreasing and bounded, so convergent. Now, take limits in $U_n = \frac1{2+U_{n-1}}$.

Answer 5

Interpret the map $$T:\ u\mapsto {1\over 2+u}\tag{1}$$ as a Moebius transformation of the complex Riemann sphere $\bar{\mathbb C}:={\mathbb C}\cup\{\infty\}$. Solving the equation $T(u)=u$ gives the two fixed points $$-1+\sqrt{2},\qquad -1-\sqrt{2}\ .$$ We therefore introduce a new complex coordinate $z$ on $\bar{\mathbb C}$ via $$z:={u+1-\sqrt{2}\over u+1+\sqrt{2}}\ ,\quad {\rm resp.}\quad u={(1+\sqrt{2})z+\sqrt{2}-1 \over 1-z}\ .$$ In this way the two fixed points of $T$ obtain the $z$-coordinates $0$ and $\infty$. In fact we obtain the following representation of $T$ in terms of $z$: $$\hat T:\quad z\mapsto \lambda\>z,\qquad \lambda:=-{2-\sqrt{2}\over2+\sqrt{2}}\doteq-0.1716\ .$$ This shows that $z=0$ is an attractive fixed point of $\hat T$, whatever the initial point $Z_0\in{\mathbb C}$ is; but of course $\hat T(\infty)=\infty$. Returning to to $(1)$ this implies that $$\lim_{n\to\infty} U_n=\sqrt{2}-1$$ for all initial points $U_0\in \bar{\mathbb C}\setminus\{-1-\sqrt{2}\}$.