5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Yup, interestingly enough, almost all "Fibonacci-like" sequences (in that they start with two seed values and then recursively define the successive terms by the addition of the previous two), except for certain trivial examples, have the ratio of successive terms converge to $\phi$. Another noteworthy such sequence is that of the Lucas numbers (with seeds $L_1 = 2$ and $L_2 = 1$, which actually is a lot "neater" than the Fibonacci sequence in this respect. $\endgroup$ – Eevee Trainer Nov 16 '18 at 8:26
  • 3
    $\begingroup$ As for the notion of $\phi$'s conjugate being the ratio of successive terms, no, at least ignoring trivial examples. You could analogize this in terms of "stable" and "unstable" solutions: the conjugate is unstable, where the regular one is stable. In the case of $\phi$'s conjugate, unless you somehow trivially start with that conjugate as the ratio of successive terms (see Robert Z's answer), this means that successive terms eventually diverge away from it. Showing this lack of stability isn't trivial though and I'm mostly parroting other facts and don't feel qualified to elaborate on it. $\endgroup$ – Eevee Trainer Nov 16 '18 at 8:32
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Thank you, your answer gives me the relation $a_0$ and $a_1$ must fulfill in order to make the limit $\frac{1-\sqrt{5}}{2}$. $\endgroup$ – TheAverageHijano Nov 16 '18 at 15:37
6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ So, basically if $A\neq 0$, the limit will be the golden ratio, and if $A=0$ and $B\neq 0$, the ratio will be $\frac{1-\sqrt{5}}{2}$, right? $\endgroup$ – TheAverageHijano Nov 16 '18 at 8:40
  • $\begingroup$ Yes, that's true. $\endgroup$ – Robert Z Nov 16 '18 at 8:42
  • $\begingroup$ Robert Z could you prove the thing about $a_n$? $\endgroup$ – AryanSonwatikar Nov 17 '18 at 4:56
  • $\begingroup$ @AryanSonwatikar This is a standard result about "homogeneous linear recurrences". See math.stackexchange.com/questions/65011/… $\endgroup$ – Robert Z Nov 17 '18 at 6:55
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice, I didn't think about stability theory to explain my question. It's nice that we can approach the problem from different but equivalent perspectives. $\endgroup$ – TheAverageHijano Nov 16 '18 at 15:42
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Actually, $a_0=1$ and $a_1=\frac{1-\sqrt{5}}{2}$ is one of the combinations that will make $\lim_{n\rightarrow\infty}\frac{a_n}{a_{n-1}}=\frac{1-\sqrt{5}}{2}$ (see Melody's answer). Multiplying both sides by x (if $x\neq 0$) shouldn't give illogical answers. Whether they have actual/physical meaning or not is another matter. $\endgroup$ – TheAverageHijano Nov 16 '18 at 15:48
  • $\begingroup$ That is true, but my answer says integers. If you take $a_0=1$ , and round off the values to the nearest integer, you get the sequence: $1,-1,0,-1..$ and here the limit suddenly tends to negative infinity because of the third term. $\endgroup$ – AryanSonwatikar Nov 17 '18 at 2:56
  • $\begingroup$ Also, I'm not well versed with matrices and vectors so Melody's answer is obscure for me. $\endgroup$ – AryanSonwatikar Nov 17 '18 at 3:00
  • $\begingroup$ Also, for the sequence you get, the Fibonacci-ness is followed only upto the fourth term after which if we follow the ratio and if we follow the Fibonacci-ness we get two different sequences. $\endgroup$ – AryanSonwatikar Nov 17 '18 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.