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

Question

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$?

Answer 1

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}$.

Answer 2

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^* $$

Answer 3

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.$

Answer 4

$$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}$$

Answer 5

I think that the key is to notice the recursive relation: $x_{n+1} = 1 + \frac{1}{x_n}$.

Since $x_n=f_{n+1}/f_n=1+f_{n-1}/f_n$, then it is easy to see that $x_{n+1}=1+f_n/f_{n+1}=1+1/x_n$. Now, consider the subsequence $(x_{n+1})_{n=1}$. Given that we already know $\lim x_n = L$, then $\lim x_{n+1} = L$, so:

$$ L = 1+1/L \\ L=\frac{1\pm \sqrt{5}}{2} $$

Also, given that $(x_n)$ is increasing, it must be that $L=\frac{1+\sqrt{5}}{2}$.