Does $a_{n}/a_{n-1}$ converge to the golden ratio for all Fibonacci-like sequences?

Question

Yesterday a friend challenged me to prove that $$\lim_{n\rightarrow\infty}\frac{a_n}{a_{n-1}}=\varphi\; ,$$ where $\varphi$ is the golden ratio, for the Fibonacci series.

I started rewriting the limit as

$$\lim_{n\rightarrow\infty}\frac{a_n}{a_{n-1}}=\lim_{n\rightarrow\infty}\frac{a_{n-1}+a_{n-2}}{a_{n-1}}=\lim_{n\rightarrow\infty}1+\frac{a_{n-2}}{a_{n-1}}\; .$$

If the sequence $b_n=\frac{a_n}{a_{n-1}}$ is convergent,

$$\lim_{n\rightarrow\infty}\frac{a_{n-2}}{a_{n-1}}=\left(\lim_{n\rightarrow\infty}\frac{a_n}{a_{n-1}}\right)^{-1}\; .$$

Renaming the desired limit $x$, we obtain the quadratic equation

$$x=1+\frac{1}{x}$$ $$x^2-x-1=0$$

if $x\neq 0$. Therefore, if $b_n$ is convergent, it must be equal to $\frac{1+\sqrt{5}}{2}$ or $\frac{1-\sqrt{5}}{2}$.

Since $a_n>0$, $b_n>0, \forall n$, so the limit must be equal to $\varphi=\frac{1+\sqrt{5}}{2}$.

This proof made me think that I didn't make use of the initial values of the sequence, so it must hold true for any sequence where $a_{n}=a_{n-1}+a_{n-2}$. The first question is, is $a_{n}/a_{n-1}$ convergent for all Fibonacci-like sequences?

The second and most intriguing for me is, is there any Fibonacci-like sequence where the limit is $\frac{1-\sqrt{5}}{2}$? Since this solution is negative, $a_n$ should change its sing with each $n$, but I couldn't find any values for $a_0$ and $a_1$, which would lead me to this case. If the answer to this question is no, what mathematical sense does this negative solution have?

Answer 1

One way to look at this problem is that if $a_{n+1}=a_n+a_{n-1}$, then we we have $$\begin{pmatrix}0&1\\1&1\end{pmatrix}\begin{pmatrix}a_{n-1}\\a_n\end{pmatrix}=\begin{pmatrix}a_n\\a_{n+1}\end{pmatrix}.$$

The eigenvalues of the matrix

$$\begin{pmatrix}0&1\\1&1\end{pmatrix}$$

are $$\dfrac{1+\sqrt{5}}{2},\dfrac{1-\sqrt{5}}{2}.$$

These have corresponding eigenvectors $v_1,v_2$ which span $\mathbb{R}^2$. This leads us to the conclusion that $$\begin{pmatrix}a_1\\a_2\end{pmatrix}=cv_1+bv_2,$$ and if $c\not=0,$ then $v_1$ will dominate the sequence, and we can show the ratios converge to $(1+\sqrt{5})/2.$ This leads us to the conclusion that if we want a Fibonacci like sequence to have ratios converging to $(1-\sqrt{5})/2$, then we must have $$\begin{pmatrix}a_1\\a_2\end{pmatrix}=bv_2$$ for some non zero $b\in\mathbb{R}$. So to determine all such sequences we simply have to have an eigenvector $v_2$ corresponding to $(1-\sqrt{5})/2$. One such eigenvector is $$\begin{pmatrix}1\\\dfrac{1-\sqrt{5}}{2}\end{pmatrix}.$$

Answer 2

You showed that if a limit exists for $a_{n}/a_{n-1}$ and $a_n>0$, then it is $\frac{1+\sqrt{5}}{2}$. Actually if $(a_n)_{n\geq 0}$ is any sequence which satisfies the recurrence $a_n=a_{n-1} + a_{n-2}$ then there exist $A$ and $B$ such that $$a_n=A\cdot \left(\frac{1+\sqrt{5}}{2}\right)^n+B\cdot \left(\frac{1-\sqrt{5}}{2}\right)^n$$ where $A$ and $B$ depend on the initial terms $a_0$ and $a_1$.

So what is $\lim_{n\rightarrow\infty}\frac{a_n}{a_{n-1}}$ in the general case?

Consider for example the case when $A=0$ and $B\not=0$. What is the limit?

Answer 3

Yes, $a_n\over a_{n-1}$ is convergent for any Fibonacci-esque sequence(with integers), and this happen to be the golden ratio, $\varphi $. The limit $1-\sqrt{5}\over 2$ will never occur for a Fibonacci-esque sequence. The negative solution crops up because you multiply both sides by $x$ when you solve $x=1+\frac{1}{x}$ leading to an extra solution. But this value is useful for calculating the value of the $n^{th}$ term of the Fibonacci sequence. $$ F_n=\frac{\varphi^n - (\frac{-1}{\varphi})^n}{\sqrt{5}}$$ Hope this helps.

Answer 4

Here is a another view of this. We have $b_n=a_n/a_{n-1}$ and $$b_{n+1}=1+\frac1{b_n},\tag{*}$$ or, \begin{align*} b_{n+1}&=1+\frac1{1+\cfrac1{b_{n-1}}}=1+\cfrac1{1+\frac1{1+\frac1{1+\frac1{1+\cdots}}}}. \end{align*} We should be clear about what we actually mean by an expression like this. One way that we could think about it is to starting with some constant like $1$, and then repeatly applying the function $f(x)=1+\dfrac 1x$, \begin{align*} c&=1&&=1.000\dots\\ \color{yellow}{f(}c\color{yellow}{)}&=\color{yellow}{1+\frac1{\color{black}{1}}}&&=2.000\dots\\ \color{orange}{f(}\color{yellow}{f(}c\color{yellow}{)} \color{orange}{)}&=\ \color{orange}{1+\frac{1}{\color{yellow}{1+\frac1{\color{black}{1}}}}}&&=1.500\dots\\ \color{magenta}{f(}\color{orange}{f(}\color{yellow}{f(}c\color{yellow}{)} \color{orange}{)}\color{magenta}{)}&=\color{magenta}{1+\frac 1{ \color{orange}{1+\frac{1}{\color{yellow}{1+\frac1{\color{black}{1}}}}}}}&&=1.667\dots\\ \color{violet}{f(}\color{magenta}{f(}\color{orange}{f(}\color{yellow}{f(}c\color{yellow}{)} \color{orange}{)}\color{magenta}{)}\color{violet}{)}&=\color{violet}{1+\frac 1{\color{magenta}{1+\frac 1{ \color{orange}{1+\frac{1}{\color{yellow}{1+\frac1{\color{black}{1}}}}}}}}}&&=1.600\dots \end{align*} Symbolly what we get is more and more like our infinite fraction. If we start with $-1/\varphi$, \begin{align*} c&=-1/\varphi&&=-0.618\dots\\ \color{yellow}{f(}c\color{yellow}{)}&=\color{yellow}{1+\frac1{\color{black}{-1/\varphi}}}&&=-0.618\dots\\ \color{orange}{f(}\color{yellow}{f(}c\color{yellow}{)} \color{orange}{)}&=\ \color{orange}{1+\frac{1}{\color{yellow}{1+\frac1{\color{black}{-1/\varphi}}}}}&&=-0.618\dots\\ \color{magenta}{f(}\color{orange}{f(}\color{yellow}{f(}c\color{yellow}{)} \color{orange}{)}\color{magenta}{)}&=\color{magenta}{1+\frac 1{ \color{orange}{1+\frac{1}{\color{yellow}{1+\frac1{\color{black}{-1/\varphi}}}}}}}&&=-0.618\dots\\ \color{violet}{f(}\color{magenta}{f(}\color{orange}{f(}\color{yellow}{f(}c\color{yellow}{)} \color{orange}{)}\color{magenta}{)}\color{violet}{)}&=\color{violet}{1+\frac 1{\color{magenta}{1+\frac 1{ \color{orange}{1+\frac{1}{\color{yellow}{1+\frac1{\color{black}{-1/\varphi}}}}}}}}}&&=-0.618\dots \end{align*} So no matter how many times we apply it, we're staying fixed at $-1/\varphi$. But even then, with the aid of a calculator, if we start with a random number $\neq-1/\varphi$ (even it's really close to $-1/\varphi$) and perform iteration $x\to x+\dfrac 1x$ again and again, we eventually end up at $1.618...=\varphi$. So,

why the fixed point $\varphi$ favored above the other one $-1/\varphi$?

The transformational understanding of derivatives is going to be helpful for understanding this set up. Now we know that $\varphi$ and $-1/\varphi$ stay fixed in place during this iteration process. But zoom in on a neighborhood around $\varphi$, during each iteration, points in that region get contracted around $\varphi$, meaning that the function $1+\dfrac 1x$ has a derivative with a magnitude that is less than $1$ at this input. In fact, the derivative works out around to be $$\left|\frac{df}{dx}(\varphi)\right|\approx |-0.38|<1,$$ meaning that each repeated application scrunches the neighborhood around this number smaller and smaller like a gravitational pull towards $\varphi$.

Conversely, at $-1/\varphi$, the magnitude of the derivative actually has a magnitude greater than $1$, $$\left|\frac{df}{dx}\left(-\frac 1\varphi\right)\right|\approx |-2.62|>1,$$ so points near the fixed point are repelled away from it. We can see that they get stretched by more than a factor of $2$ in each iteration. (They also get flipped around because the derivative is negative here, but the salient fact of stability is just the magnitude.)

We will call $\varphi$ a "stable fixed point", and $-1/\varphi$ an "unstable fixed point". As we can see the stability of a fixed point is determined by whether or not of its derivative is bigger or smaller than $1$. And this explains why $\varphi$ always shows up in the limit.

Reference: 3Blue1Brown.