# Prob. 3, Sec. 3.4, in Bartle & Sherbert's INTRO TO REAL ANALYSIS, 4th ed: Does this sequence converge?

Let the sequence $\left( f_n \right)_{n \in \mathbb{N} }$ be given by $$f_1 \colon= 1, \qquad f_2 \colon= 1, \qquad \mbox{ and } \qquad f_n \colon= f_{n-1} + f_{n-2} \ \mbox{ for all } n \in \mathbb{N} \mbox{ such that } n > 2.$$ That is, $\left( f_n \right)_{n \in \mathbb{N} }$ is the famous Fibonacci sequence.

Now let the sequence $\left( x_n \right)_{n \in \mathbb{N} }$ be given by $$x_n \colon= \frac{f_{n+1} }{f_n} \ \mbox{ for all } n \in \mathbb{N}.$$ Thus we have $$x_1 = \frac{f_2}{f_1} = 1,$$ and $$x_n = \frac{ f_n + f_{n-1} }{f_n} = 1 + \frac{f_{n-1}}{f_n} \ \mbox{ for all } n \in \mathbb{N} \mbox{ such that } n \geq 2.$$

Does the sequence $\left( x_n \right)_{n \in \mathbb{N} }$ converge in $\mathbb{R}$? If so, then what is $\lim_{n \to \infty} x_n$?

My Attempt:

First, we note that $$f_1 = f_2 = 1, \ f_3 = f_2+ f_1 = 2, \ f_4 = f_3 + f_2 = 3, \ f_5 = f_4 + f_3 = 5, \ f_6 = f_5 + f_4 = 8, \\ f_7 = f_6 + f_5 = 13, \ f_8 = f_7 + f_6 = 21, \ f_9 = f_8 + f_7 = 34, \ f_{10} = f_9 + f_8 = 55. \\ f_{11} = f_{10} + f_9 = 89, \ f_{12} = f_{11} + f_{10} = 144, \ f_{13} = f_{12} + f_{11} = 233, \\ f_{14} = f_{13} + f_{12} = 377.$$ So $$x_1 = \frac{f_2}{f_1} = 1, \ x_2 = \frac{f_3}{f_2} = 2, \ x_3 = \frac{f_4}{f_3} = \frac{3}{2}, \ x_4 = \frac{f_5}{f_4} = \frac{5}{3}, \ x_5 = \frac{f_6}{f_5} = \frac{8}{5}, \\ x_6 = \frac{f_7}{f_6} = \frac{13}{8}, \ x_7 = \frac{f_8}{f_7} = \frac{21}{13}, \ x_8 = \frac{f_9}{f_8} = \frac{34}{21}, \ x_9 = \frac{f_{10}}{f_9} = \frac{55}{34}, \ x_{10} = \frac{f_{11}}{f_{10}} = \frac{89}{55}, \\ x_{11} = \frac{f_{12}}{f_{11}} = \frac{144}{89}, \ x_{12} = \frac{f_{13}}{f_{12}} = \frac{233}{144}, \ x_{13} = \frac{f_{14}}{f_{13}} = \frac{377}{233}.$$

From these calculations we notice that $$x_1 < x_3 < x_5 < x_7 < x_9 < x_{11} < x_{13} < 2,$$ and $$x_2 > x_4 > x_6 > x_8 > x_{10} > x_{12} > 0.$$

How to proceed from here? How to show that $$x_{2n-1} < x_{2n+1} \ \mbox{ and } \ x_{2n} > x_{2n+2} \ \mbox{ for all } n \in \mathbb{N}?$$

And, how to show that the subsequence $\left( x_{2n-1} \right)_{n \in \mathbb{N} }$ of $\left(x_n \right)_{n \in \mathbb{N}}$ is bounded above?

Can we treat it as obvious that the subsequence $\left( x_{2n} \right)_{n \in \mathbb{N} }$ of $\left( x_n \right)_{n \in \mathbb{N} }$ is bounded from below by $0$?

Once we have shown that the subsequence $\left( x_{2n-1} \right)_{n \in \mathbb{N} }$ is increasing and bounded from above, then let us put $$x^\prime \colon= \lim_{n \to \infty} x_{2n-1}.$$

And, once we have shown that the subsequence $\left( x_{2n} \right)_{n \in \mathbb{N} }$ is decreasing and bounded from below, then let us put $$x^* \colon= \lim_{n \to \infty} x_{2n}.$$

How to proceed from here? Can we show that $x^{\prime} = x^*$? And, once we have shown this, then how to find $\lim_{n \to \infty} x_n$?

• You've wrote $x_n = 1 + \frac{1}{x_{n-1}}$! I know it's a bit of stretch - suppose the limit exists. Then, if denoted by $L$: $L = 1 + \frac{1}{L}$. Solve ... – dEmigOd Mar 31 '18 at 6:15
• Why can't you just write the sequence in the title? Not everyone have this book on end. Clickbait titles are terrible. (The same, by the way, goes to the list of questions that have similar titles which you recently posted.) – Asaf Karagila Mar 31 '18 at 7:59

There is a relationship between the Fibonacci sequence and the golden ratio.

Let $\phi= \frac{1+\sqrt5}2$, the golden ratio, $\phi > 1$. We know that

$$f_n = \frac{\phi^n -(-\phi)^{-n}}{\sqrt{5}}$$

$$x_n = \frac{f_{n+1}}{f_n}=\frac{\phi^{n+1}-(-\phi)^{-(n+1)}}{\phi^n - \phi^{-n}}=\frac{\phi-(-\phi)^{-(2n+1)}}{1-\phi^{-2n}}$$

As $n \to \infty$, $x_n \to \phi= \frac{1+\sqrt{5}}{2}$.

• how do we obtain the relation $f_n = \frac{ \phi^n - (-\phi)^{-n} }{\sqrt{5}}$? – Saaqib Mahmood Apr 1 '18 at 5:28
• Depending on your background. We can either do it by diagonalization or characteristic equation. – Siong Thye Goh Apr 1 '18 at 5:37
• I'd appreciate if you could include both of these two approaches in a P.S. in your answer. – Saaqib Mahmood Apr 1 '18 at 5:55
• read section $3$ and $4$ of this link for the diagonalization approach and also the previous link that I provided. – Siong Thye Goh Apr 1 '18 at 6:05
• Also, relevant link that show proofs for the Binet formula. – Siong Thye Goh Apr 1 '18 at 6:18

Hints. Observe that $\{x_n\}$ satisfies the recursion $$x_{n+1}=1+\frac{1}{x_n}=f(x_n), \quad x_1=1.$$ Clearly, $x_n \ge 1$, for all $n\in\mathbb N$. Then show that, for $x,y>0$, $$x<y<\frac{1+\sqrt{5}}{2}\quad\Longrightarrow\quad f(x)>f(y)>\frac{1+\sqrt{5}}{2} \quad\text{and}\\ x>y>\frac{1+\sqrt{5}}{2}\quad\Longrightarrow\quad f(x)<f(y)<\frac{1+\sqrt{5}}{2}$$ and $\,\,f\big(\frac{1+\sqrt{5}}{2}\big)=\frac{1+\sqrt{5}}{2}$. Also, if $x>0$ and $x\ne \frac{1+\sqrt{5}}{2}$, then $$\Big|\,x-\frac{1+\sqrt{5}}{2}\Big|>\Big|\,f\big(f(x)\big)-\frac{1+\sqrt{5}}{2}\Big|.\, \tag{1}$$ To see this, first $f\big(f(x)\big)=1+\frac{1}{f(x)}=1+\frac{1}{1+\frac{1}{x}}=\frac{2x+1}{x+1}$, and then, for $w=\frac{1}{2}(\sqrt{5}+1)$, $$x-f\big(f(x)\big)=x-\frac{2x+1}{x+1}=\frac{x^2-x-1}{x+1}$$ hence $x-f\big(f(x)\big)>0$, when $x>w$ and $x-f\big(f(x)\big)<0$, for $x\in(0,w)$. Also, $$f\big(f(x)\big)>w\quad\Longleftrightarrow\quad \frac{2x+1}{x+1}-w>0 \quad\Longleftrightarrow\quad x>\frac{w-1}{2-w}=w.$$

Hence $$x_1<x_3<\cdots<x_{2n-1}<\frac{1+\sqrt{5}}{2}<x_{2n}<\cdots<x_4<x_2,$$ Thus both subsequences $\{x_{2n-1}\}$ and $\{x_{2n}\}$ converge to say $x_*$ and $x^*$, respectively and $$x_*\le \frac{1+\sqrt{5}}{2}\le x^*$$ Finally, use $(1)$ to show that $$x_*= \frac{1+\sqrt{5}}{2}= x^*$$

• how does the following assertion in your answer hold? If $x>0$ and $x\ne \frac{1+\sqrt{5}}{2}$, then $$\Big|\,x-\frac{1+\sqrt{5}}{2}\Big|>\Big|\,f\big(f(x)\big)-\frac{1+\sqrt{5}}{2}\Big|\, \tag{1}$$ – Saaqib Mahmood Apr 1 '18 at 5:52
• @SaaqibMahmood See my improved answer. – Yiorgos S. Smyrlis Apr 1 '18 at 8:01

$$x_n = \frac{f_{n+1} }{f_n} \implies x_{n+1}= 1+\frac {1}{x_n}$$

Thus $x_{2n-1}$ is increasing while $x_{2n}$ is decreasing, and we have nested intervals.

For both subsequences, the limit satisfies $$L= \frac {2L+1}{L+1}$$

Upon solving for L we get, $$L= \frac {1+\sqrt 5}{2}$$

Thus the sequence converges to the golden ratio, and $$L=\frac {1+\sqrt 5}{2}$$

• how do we conclude from the relation $$x_{n+1} = 1 + \frac{1}{x_n}$$ that $x_{2n-1}$ is increasing while $x_{2n}$ is decreasing. It could just as well be the other way around, couldn't it? – Saaqib Mahmood Apr 1 '18 at 5:32
• @SaaqibMahmood $x_{n+1} -x_{n}= \{0,0,-1/2,1/6,-1/15,..\}$is an alternating sequence. – Mohammad Riazi-Kermani Apr 1 '18 at 9:23

It is convenient to allow the recursive formula to hold for all $n\in \Bbb Z.$

(I). The homogeneous difference equation $F(n+2)-F(n+1)-F(n)=0$ has an associated polynomial equation $x^2-x-1=0,$ which has two solutions $g=(1+\sqrt 5\;)/2$ and $h=(1-\sqrt 5)/2=-1/g.$

Observe that if $x\in \{g,h\}$ and $G(n)=x^n$ then $G(n+2)-G(n+1)-G(n)=0.$

Given any values $F(0)=A$ and $F(1)=B,$ there exist unique $C,D$ such that $C+D=A$ and $Cg+Dh=B.$ By induction on $n$ we then have $F(n)=Cg^n+Dh^n$ for all $n.$

For example $F(2)=F(1)+F(0)=(Cg+Dh)+(C+D)=C(1+g)+D(1+h) =Cg^2+Dh^2.$

(II). For the Fibonacci sequence we have $F(0)=0$ and $F(1)=1,$ and we find $C=1/\sqrt 5\;$ and $D=-1/\sqrt 5\;.$ So $F(n)=(g^n-h^n)/\sqrt 5.$

Since $g>1$ and $0>h>-1$ it is now easily seen that $\lim_{n\to \infty}\frac {F(n+1)}{F(n)}=g.$

BTW . We can see at the beginning that if $L=\lim_{n\to \infty}\frac {f_{n+1}}{f_n}$ exists then (obviously) $L\geq 1,$ and that $L=\lim x_{n+1}=$ $\lim \frac {f_{n+2}}{f_{n+1}}=$ $\lim \frac {f_{n+1}+f_n}{f_{n+1}}=$ $\lim (1+x_n^{-1})=$ $1+L^{-1},$ implying $(L^2=L+1)\land (L\geq 1),$ implying $L=g.$

• how are you? Nice to hear from you again! There is one point that I couldn't grasp in your answer. How does the following hold? Given any values $F(0)=A$ and $F(1)=B,$ there exist unique $C,D$ such that $C+D=A$ and $Cg+Dh=B.$ – Saaqib Mahmood Apr 1 '18 at 5:43
• @SaaqibMahmood . It is just a matter of solving the 2 simultaneous linear equations for the variables $C,D$, – DanielWainfleet Apr 1 '18 at 16:33