# Suppose that {$a_n$} is the Fibonacci sequence, and $b_n=\frac{a_{n+1}}{a_n}$. Prove that {$b_n$} converges to the Golden Number.

This is an exercise in my Analysis book that I find difficult. Suppose that {$a_n$} is the Fibonacci sequence, and $b_n=\frac{a_{n+1}}{a_n}$. Prove that {$b_n$} converges to the Golden Number.

First, of course, one has to prove that {$b_n$} does converge. I think since $a_n$ is increasing, and $a_{n+1}-a_n>a_n-a_{n-1}$, {$b_n$} is decreasing. Now since both the numerator and denominator are positive, {$b_n$} is bounded below by $0$. That means {$b_n$} must converge.

Now how to prove that {$b_n$} actually converges to $\frac{1+\sqrt5}{2}$ I don't know. I tried taking limits of $b_{n+1}$ and $b_n$ but that got messy and didn't seem to lead anywhere.

How do I solve this?

• what do you know /are allowed to use about Fibonacci's Numbers? – G Cab Nov 20 '16 at 17:22
• Just the recursive definition. – QuestionMaker Nov 20 '16 at 17:23
• The sequence $b_n$ isn't decreasing. For example, $5/3$ isn't smaller than $3/2$. – Wojowu Nov 20 '16 at 17:39
• Binet's formula for the Fibonacci sequence is helpful and just a google search away. – Oiler Nov 20 '16 at 17:51

First, from the definition of the sequence $\{b_n\}$: $$b_{n+1}=\frac{a_{n+2}}{a_{n+1}}$$ But $\{a_n\}$ is the Fibonacci sequence, so $a_{n+2}=a_{n+1}+a_n$, then: $$b_{n+1}=\frac{a_{n+1}+a_n}{a_{n+1}}=1+\frac{a_n}{a_{n+1}}=1+\frac{1}{b_n}$$ So, the equence $\{b_n\}$ satisfies: $$b_{n+1}=\frac{b_n+1}{b_n}$$ Then, if the limit exists, let's say that it is $l$, it must satisfy the equation: $$l=\frac{l+1}{l}$$ That's equivalent to: $$l^2-l-1=0$$ Now solving this equation we find $l=\frac{1\pm \sqrt{5}}{2}$, but the sequence is bounded below by $0$ and $\frac{1-\sqrt{5}}{2}<0$ so $\lim b_n$ cannot be $\frac{1-\sqrt{5}}{2}$, then we conclude that: $$l=\frac{1+\sqrt{5}}{2}$$

• "...if the limit exists..." You ought to prove this part too. – Wojowu Nov 20 '16 at 17:38
• Oh, sorry, I thought that it was prooved in the question, my mistake. – Dieter Enns Nov 20 '16 at 17:41
• I like to write it out as $$\phi=\cfrac1{1+\frac1{1+\frac1\ddots}}$$ – Simply Beautiful Art Nov 20 '16 at 17:44
• – Simply Beautiful Art Nov 20 '16 at 17:46
• @DieterEnns: it is "proven", but the proof is flawed since $b_n$ is not decreasing. – robjohn Nov 20 '16 at 19:29

Using induction, we will prove $$F_{n+1}F_{n-1}-F_n^2=(-1)^n\tag{1}$$ Note that $F_2F_0-F_1^2=-1$.
Assume that $F_nF_{n-2}-F_{n-1}^2=(-1)^{n-1}$. Then \begin{align} F_{n+1}F_{n-1}-F_n^2 &=(F_n+F_{n-1})F_{n-1}-F_n^2\\ &=F_{n-1}^2-F_n(F_n-F_{n-1})\\ &=F_{n-1}^2-F_nF_{n-2}\\ &=-(-1)^{n-1}\\ &=(-1)^n\tag{2} \end{align} Therefore, $(1)$ is true for $n\ge1$.

Dividing $(1)$ by $F_nF_{n-1}$ gives $$\frac{F_{n+1}}{F_n}-\frac{F_n}{F_{n-1}}=\frac{(-1)^n}{F_nF_{n-1}}\tag{3}$$ Since $F_{n+1}\ge F_n$, \begin{align} \frac{F_{n+2}F_{n+1}}{F_{n+1}F_n} &=\frac{F_{n+2}}{F_n}\\ &=\frac{F_{n+1}}{F_n}+1\\[6pt] &\ge2\tag{4} \end{align} Therefore, for $n\ge1$, $$F_nF_{n+1}\ge2^{n-1}\tag{5}$$ Thus, $(3)$ and $(5)$ show that \begin{align} \lim_{n\to\infty}\frac{F_{n+1}}{F_n} &=\frac{F_2}{F_1}+\lim_{n\to\infty}\sum_{k=2}^n\frac{(-1)^k}{F_kF_{k-1}}\\ &=1+\sum_{k=2}^\infty\frac{(-1)^k}{F_kF_{k-1}}\tag{6} \end{align} converges.

The recursion for $F_n$ implies \begin{align} 0 &=\lim_{n\to\infty}\frac{F_{n+2}-F_{n+1}-F_n}{F_n}\\ &=\lim_{n\to\infty}\frac{F_{n+2}}{F_{n+1}}\frac{F_{n+1}}{F_n}-\lim_{n\to\infty}\frac{F_{n+1}}{F_n}-1\\ &=\left(\lim_{n\to\infty}\frac{F_{n+1}}{F_n}\right)^2-\lim_{n\to\infty}\frac{F_{n+1}}{F_n}-1\tag{7} \end{align} Equation $(7)$ implies that $$\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\frac{1\pm\sqrt5}2\tag{8}$$ Since $\frac{F_{n+1}}{F_n}\ge1$, $(8)$ implies $$\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\frac{1+\sqrt5}2\tag{9}$$