# Why do sequences $(x_n)$ of real numbers defined by $x_{n+1}=1+\frac 1{x_n}$ nearly always converge to the golden ratio?

I want to prove that the sequence $(x_n)$ of real numbers defined by $x_{n+1}=1+\frac 1{x_n}$ and $x_0\in\Bbb R\setminus \left\{a_n\ \left|\ a_0=0 \text{ and } a_{n+1}=\frac 1{a_n-1} \right.\right\}$ is convergent. It is not monotonic, because $f(x)=1+\frac 1 x$ is a decreasing function, but I have figured out that $x_{n+1}>x_n$ when $x_n \in \left(-\infty,\frac 1 2 -\frac {\sqrt 5} 2\right)\cup\left(0, \frac 1 2 +\frac {\sqrt 5}2\right)$ with $x_{n+1}>0$ when $x_n<-1$, and $x_{n+1}< x_n$ when $x_n \in \left(\frac 1 2 -\frac {\sqrt 5} 2,0\right)\cup \left(\frac 1 2 +\frac {\sqrt 5} 2,\infty \right)$. The mapping $x\mapsto1+\frac 1 x$ is not a strong contraction, so I cannot use Banach's Fixed Point Theorem.

Secondly, how can I prove that $\frac 1 2 +\frac{\sqrt 5} 2$ is the limit of the sequence when $x_0\neq \frac 1 2 -\frac{\sqrt 5}2$?

• It doesn't converge for $x_0=-1/2,-2/3,-3/5,\dots$ since the sequence hits $0$ then. – Wojowu Nov 13 '16 at 8:48
• I don't understand the set construction end of line 1 – Prince M Nov 13 '16 at 9:01
• @PrinceM I'm trying to say that I only want to consider $x_0$ that doesn't lead to a term in the sequence equalling $0$. – ahorn Nov 13 '16 at 9:04
• I could have said, "Let $x_0=1$" but I want to have a proof that isn't specific to one number, because the sequence converges for many $x_0\in \Bbb R$. – ahorn Nov 13 '16 at 9:09
• If the sequence starting with $x_0$ converges, say to $x$, then $x=1+\frac{1}{x}$ so $x^2-x+1=0$, meaning that $$x=\frac{1}{2}\pm\frac{1}{2}\sqrt{5}.$$ – Servaes Nov 13 '16 at 12:08

You can proceed as follows. It will suffice to show that there is an index $r$ such that $x_r> 0$.

If $x_0\in A_0=(0,\infty)$, then $r=0$ and we are done.

If $x_0\in B_0=(-\infty, -1)$, then $r=1$ and we are done.

So we may assume without loss that $x_0\in (-1,0)$.

If $x_0\in A_1=\left(-\frac{1}{2},0\right)$, then $x_1\in B_0$, $r=2$ and we are done. So we may assume without loss that $x_0\in\left(-1,-\frac{1}{2}\right)$.

If $x_0\in B_1=\left(-1,-\frac{2}{3}\right)$, then $x_1 \in A_1$, $r=3$ and we are done. So we may assume without loss that $x_0\in\left(-\frac{2}{3},-\frac{1}{2}\right)$.

Continuing this way, we obtain (for $n\geq 1$) the two families $A_n=\left(-u_{n+1},-u_{n}\right), B_n=\left(\frac{-1}{u_{n}+1},\frac{-1}{u_{n+1}+1}\right)$ where $(u_n)$ is defined by $u_1=0$ and $u_{n+1}=\frac{u_n+1}{u_n+2}$. It is easy to check that $u_n$ stays in $(0,1)$, is increasing and converges to $\frac{-1+\sqrt{5}}{2}$.

Equally easily, we have $f(B_n)\subseteq A_n$ and $f(A_n)\subseteq B_{n-1}$, whence $r=2n$ whenever $x_0\in A_n$ and $r=2n+1$ whenever $x_0\in B_n$.

So the only case that's left is when $x_0$ is not in any of the $A_n$ or $B_n$. This means that $x_0$ is at one of the endpoints of $A_n,B_n (n\geq 1)$, i.e. $x_0$ is either one of your $a_k$'s or is $\frac 1 2 - \frac {\sqrt 5}2$.

Edit by the OP (ahorn):

We have seen from Ewan's answer that we can consider $x_0>0$ without loss of generality. What follows is an attempt to solidify the claim that $(x_n)$ converges in this case. Taking advice from Ewan, let $g=f\circ f$ where $f(x):=1+\frac 1 x$. That is, $g(x)=2-\frac 1{x+1}$ which is an increasing function.

Let $x_0\in(0,\phi)$, where $\phi=\frac 1 2 +\frac{\sqrt 5} 2$.

Since $x<g(x)<\phi=\sup\{g(x)\ |\ x\in(0,\phi) \}$ when $x\in(0,\phi)$, $$x_{2n}<g(x_{2n})=x_{2n+2}<\phi=\sup\{x_{2k}\}$$ where $n, k\in \Bbb N$. So $(x_{2n})$ is an increasing sequence that converges to $\phi$.

$x_0\in(0,\phi)\implies x_{1}\in(\phi,\infty)$.

Since $x>g(x)>\phi=\inf\{g(x)\ |\ x\in(\phi,\infty) \}$ when $x\in(\phi, \infty)$, $$x_{2n+1}>g(x_{2n+1})=x_{2n+3}>\phi=\inf\{x_{2k+1}\}$$ so $(x_{2n+1})$ is a decreasing sequence that converges to $\phi$.

Now, $x_n\in(0,\phi)\implies x_{n+1}\in(\phi,\infty)$ and $x_n\in(\phi, \infty)\implies x_{n+1}\in(0, \phi)$, so $x_0\in(0,\phi)$ was chosen without loss of generality.

Suppose that for any $\epsilon>0$, $2k\geq N_1\implies|x_{2k}-\phi|<\epsilon$ and $2k+1\geq N_2\implies|x_{2k+1}-\phi|<\epsilon$. Let $N=\max\{N_1, N_2\}$ so that $n\geq N \implies |x_n-\phi|<\epsilon.$

• Now the only thing left to prove is that the sequence converges for $x_0>0$, and that the limit is $\frac 1 2 +\frac {\sqrt 5} 2$. Is there some rule to use, like the fact that $1+\frac 1 x$ is convex? – ahorn Nov 13 '16 at 14:32
• @ahom the key property is that $I=(0,\infty)$ is stable by $f$, and further $f\circ f$ is increasing on it, so if $x_0\in I$ then all the $x_k$ are in $I$, and further the sequences $(x_{2n})$ and $(x_{2n+1})$ are both monotone – Ewan Delanoy Nov 13 '16 at 14:54
• I want to conclude the proof and have now typed up a proof for $x_0>0$. I'm planning on posting it as an answer, but it is unfortunate that the proof is broken up between two answers. Should I post my answer or should I edit yours? – ahorn Nov 13 '16 at 16:00
• @ahorn Edit mine as much as you please, I probably won't re-edit anything – Ewan Delanoy Nov 13 '16 at 16:01
• Okay, just check that you agree with it. – ahorn Nov 13 '16 at 16:02

The map $x\mapsto 1+{1\over x}$ defined on ${\mathbb R}\setminus\{0\}$ can be extended to a Moebius transformation of the Riemann sphere $\bar{\mathbb C}:={\mathbb C}\cup\{\infty\}$: $$T:\quad \bar{\mathbb C}\to \bar{\mathbb C},\qquad z\mapsto {z+1\over z},\quad T(0)=\infty,\quad T(\infty)=1\ .\tag{1}$$ Its fixed points are $\alpha:={1\over2}(1+\sqrt{5})$ and $\beta={1\over2}(1-\sqrt{5})$, obtained by solving the equation $z^2-z-1=0$.

We now introduce a new complex coordinate $w$ on $\bar {\mathbb C}$, related to $z$ via $$w=\phi(z):={z-\alpha\over z-\beta},\qquad{\rm resp.}\qquad z=\phi^{-1}(w):={\alpha-\beta w\over 1-w}\ .$$ The fixed points now are $w=0$ and $w=\infty$. In fact, in terms of the new coordiate $w$ the transformation $T$ appears as $\hat T=\phi\circ T\circ\phi^{-1}$, and computes to $$\hat T:\quad \bar{\mathbb C}\to \bar{\mathbb C},\qquad w\mapsto{\beta\over\alpha}w,\quad \hat T(0)=0,\quad \hat T(\infty)=\infty\ .$$ Since $${\beta\over\alpha}=-{3-\sqrt{5}\over2}\doteq-0.382$$ we can infer that the fixed point $0$ is attracting with basin of attraction all of ${\mathbb C}$, while $\infty$ is repelling. This allows to conclude that in the original setting all initial points $x_0\ne \beta$ lead to $\lim_{n\to\infty} x_n=\alpha$ (assuming the "exception handling" described in $(1)$).

Assuming $f(x)=1+\frac{1}{x}$...

Part 1. First of all (as it was mentioned in a comment), we can't have $x_0=0$. We also can't have $x_0=-1$, because this leads to $x_1=0$. Same applies to $x_0=-\frac{1}{2}$, leading to $x_1=-1$ and $x_2=0$. By induction this applies to any $x_0=-\frac{F_{n-1}}{F_n}$, where $\{F_n\}$-Fibonacci numbers, because $f\left(-\frac{F_{n-1}}{F_n}\right)=1-\frac{F_{n}}{F_{n-1}}=-\frac{F_{n-2}}{F_{n-1}}$ eventually leading to $0$.

Part 2. Let's consider $g(x)=x-f(x)$ which is continuous, except $x=0$, and $g\left(\frac{3}{2} \right)=-\frac{1}{6}<0$ and $g\left(2\right)=\frac{1}{2}>0$. Then $\exists x_0 \in \left(\frac{3}{2},2\right): g(x_0)=0$ or $f(x_0)=x_0$. Additionally, $g'(x)=1+\frac{1}{x^2}>0$ for $x>1$ (i.e. ascending), so that $x_0$ is also unique. We can conclude that if $\lim_{n\rightarrow \infty} x_n$ exists on $\left(1,+\infty\right)$ then it's unique and between $\left(\frac{3}{2},2\right)$. But does it exist?

Part 3. We observe that $\left|f'(x)\right|=\left|\frac{1}{x^2}\right|<1,x>1$ - making $f$ a contraction on $\left[\frac{3}{2},2 \right]$, from the perspective of mean value theorem, i.e. $\exists c \in (x_{n}, x_{n+1})$ such that $|f(x_{n+1}) - f(x_{n})|=|f'(c)||x_{n+1}-x_{n}|$ or $|x_{n+2} - x_{n+1}| < \left|f'(\frac{3}{2})\right| |x_{n+1}-x_{n}|=\frac{4}{9} |x_{n+1}-x_{n}|$. Or $$|x_{n+2} - x_{n+1}| < \left(\frac{4}{9}\right)^2|x_{n}-x_{n-1}| < ... <\left(\frac{4}{9}\right)^n|x_{1}-x_{0}|$$

and $\frac{3}{2}\leq x_0\leq 2 \Rightarrow \frac{2}{3}\geq \frac{1}{x_0} \geq \frac{1}{2} \Rightarrow 2 > \frac{5}{3} \geq f(x_0)\geq \frac{3}{2}$. This can be used to show the limit exists.

Special consideration for the case $x_0 > 2$. Then

$1 < f(x_0)<\frac{3}{2}$, $2>f(f(x_0))>\frac{5}{3}$, $\frac{3}{2}<f^{(3)}(x_0)<\frac{8}{5}$, $\frac{5}{3}>f^{(4)}(x_0)>\frac{13}{8}$ ... it is squeezed in between fractions of form $\frac{F_{n+1}}{F_n}$ which leads to golden ratio.

Part 4. If we take $\forall x_0 \in \left(0,\frac{3}{2}\right)$ we have $x_1=f(x_0)>\frac{2}{3}+1>\frac{3}{2}$. From $x_1$ the sequence "falls" in the convergence zone $\left[\frac{3}{2},+\infty \right)$.

Part 5. $\forall x_0 \in \left(-\infty,-1\right)$ we have $x_0<-1 \Rightarrow -x_0>1 \Rightarrow 0< -\frac{1}{x_0} <1 \Rightarrow 0>\frac{1}{x_0} > -1 \Rightarrow x_1=f(x_0) > 0$. According to Part 3 & 4, either from $x_1$ or $x_2$ the sequence "falls" in the convergence zone $\left[\frac{3}{2},+\infty \right)$

Part 6. $\forall x_0 \in \left(-\frac{1}{2},0\right)$ we have $-\frac{1}{2} < x_0 <0 \Rightarrow \frac{1}{2} > -x_0 >0 \Rightarrow 2 < -\frac{1}{x_0} \Rightarrow -2 > \frac{1}{x_0} \Rightarrow x_1=f(x_0) < -1$ from $x_1$ we are in the Part 5 scenario.

Part 7. This time we will have to look in between $-1 < -\frac{2}{3} < -\frac{5}{8}<...<-\frac{F_{n-1}}{F_n}<...<-\frac{8}{13}< -\frac{3}{5}< -\frac{1}{2}$, considering the alternating nature of $\frac{F_{n-1}}{F_n}$, we observe that:

• $x_0 \in \left(-1, -\frac{2}{3}\right) \Rightarrow f(x_0) \in \left(-\frac{1}{2},0\right)$, this is Part 6.
• $x_0 \in \left(-\frac{3}{5}, -\frac{1}{2}\right) \Rightarrow f(x_0) \in \left(-1, -\frac{2}{3}\right)$ this is previous case now.
• ... and so on, every $A$ gets promoted to $f(A)$ previously analysed escaping eventually into convergence zone, just an example $$-\frac{F_{n-1}}{F_{n}} < x_0 < -\frac{F_{n+1}}{F_{n+2}} \Rightarrow \frac{F_{n-1}}{F_{n}} > -x_0 > \frac{F_{n+1}}{F_{n+2}} \Rightarrow \frac{F_{n}}{F_{n-1}} < -\frac{1}{x_0} < \frac{F_{n+2}}{F_{n+1}} \Rightarrow$$ $$1-\frac{F_{n}}{F_{n-1}} > 1 + \frac{1}{x_0} > 1-\frac{F_{n+2}}{F_{n+1}} \Rightarrow -\frac{F_{n-2}}{F_{n-1}} > f(x_0) > -\frac{F_{n}}{F_{n+1}}$$

The only problem is $\lim_{n\rightarrow \infty} -\frac{F_{n-1}}{F_n}$ which is $$\lim_{n\rightarrow \infty} -\frac{F_{n-1}}{F_n}=-\frac{1}{\varphi }=\frac{1-\sqrt{5}}{2}$$

For all the cases, the limit is the positive root of polynomial $x^2-x-1=0$.

• In Part 3, you in effect showed that the sequence is Cauchy on $\left[\frac 32, \infty\right)$. So, since the domain is real, the sequence converges. Is that the thinking behind your claim that "the limit exists"? – ahorn Nov 13 '16 at 21:04
• Yes, that's correct. – rtybase Nov 13 '16 at 21:06
• For $x_0>0$, this asserts that the sequence "falls" in a "convergence zone" $[\frac32,\infty)$. But $[\frac32,\infty)$ is not stable by the transformation $f:x\mapsto1+\frac1x$ (since $x>2$ implies $f(x)<\frac32$) hence I am afraid the considerations in this post do not suffice to solve the exercise. (For your future answers, I suggest that you first polish a definitive answer and only then post it on the site.) – Did Nov 15 '16 at 6:50
• @Did, I updated my answer. – rtybase Nov 15 '16 at 10:43
• Let me repeat the mathematical argument one last time: If $I=[\frac32,\infty)$, then $|f'|\leqslant\frac49$ on $I$, which is good because $\frac49<1$, but $f(I)$ is not included in $I$, which is bad since this implies that the contraction bound cannot be iterated. (Note that nearly every other consideration in your last pair of comments is offtopic, sorry to say, hence I see no point in answering them.) – Did Nov 15 '16 at 14:37

Hint: show that the sequence $x_n$ is bounded. It must then have a convergent subsequence. Can you show the whole sequence converges to the same limit?

• I would need to show that it is Cauchy. – ahorn Nov 13 '16 at 9:23