Why does every "fibonacci like" series converge to $\phi$?

Question

It's is well known that the ratio of side-by-side fibonacci numbers converge to $\phi$. But it seems by my calculations, that if one starts with any pair of numbers one will also get a ratio that converges to $\phi$. Say for example if one starts with $3$ and $4$ we get:

4   1,333333333
7   1,75
11  1,571428571
18  1,636363636
29  1,611111111
47  1,620689655
76  1,617021277
123 1,618421053
199 1,617886179
322 1,618090452
521 1,618012422
843 1,618042226

where the series is on the left and the ratio is side-by-side numbers are on the right.

I'm quite curious to know why this happens. Anyone?

Answer 1

The sequences that satisfy the linear recurrence

$$G_{n+2} = G_{n+1} + G_n$$

take the general form

$$ A \alpha^n + B \beta^n$$

where $\alpha, \beta$ are roots of

$$x^2 = x + 1 $$

If $A \ne 0$ (and $\alpha$ is the larger root), the ratio of two consecutive such terms $G_{n+1}/G_n$, converges to the larger root, which in this case is the golden ratio: $\varphi$.

$$ G_{n+1}/G_n = \frac{A \alpha^{n+1} + B \beta^{n+1}}{A \alpha^n + B \beta^n}$$

Take the larger root out ($\alpha$)

$$ = \alpha\left(\frac{A + B (\beta/\alpha)^{n+1}}{A + B (\beta/\alpha)^n}\right) \to \alpha$$

If $A = 0$ and $B \ne 0$, then it converges to $\beta$.

Answer 2

Let's define a Fibonacci-like sequence to be a sequence satisfying: $$s_n=s_{n-1}+s_{n-2}.$$ Notice that if we take two Fibonacci-like sequences and add them together, we get another Fibonacci-like sequence - that is, if $a_n$ and $b_n$ are Fibonacci-like, then so is $a_n+b_n$ - you can check the recurrence yourself. Similarly, if we scale every term of a Fibonacci-like sequence by a constant, it is still Fibonacci-like - that is, if $a_n$ is Fibonacci-like, so is $c\cdot a_n$.

This means that such sequences form a structure called a vector space - that is, if we set up a linear combination on Fibonacci-like sequences (e.g. $\alpha\cdot a_n + \beta \cdot b_n$), the result is still Fibonacci-like. However, what's crucial about this insight is that, since we can easily prove that any Fibonacci-like sequence is determined by its first two terms, then if we take two sequences $F_n$, which is the Fibonacci sequence starting with $F_0=0$ and $F_1=1$ and a similar sequence $F'_n=F_{n-1}$, which starts $F'_0=1$ then $F'_1=0$ we can show that if, for a Fibonacci-like sequence $s$ we have $$s_0=s_0\cdot F'_0+s_1\cdot F_0$$ $$s_1=s_0\cdot F'_1+s_1\cdot F_1$$ then, since the right hand side is Fibonacci-like, being a linear combination of Fibonacci-like sequences, and since the right hand sequence agrees for the first two terms, which determine the sequence, we can immediately leap to $$s_n=s_0\cdot F'_n+s_1\cdot F_n$$ or, replacing $F'$ by its definition $$s_n=s_0\cdot F_{n-1}+s_1\cdot{F_n}$$ that is to say, that $s_n$ can be written as a linear combination of the Fibonacci sequence and a shift of it. Then, the ratio of successive terms is $$\frac{s_0\cdot F_{n}+s_1\cdot F_{n+1}}{s_0\cdot F_{n-1}+s_1\cdot F_n}$$ which, if we divide both numerator and denominator by $F_n$ gives $$\frac{s_0+s_1\cdot \frac{F_{n+1}}{F_n}}{s_0\cdot \frac{F_{n-1}}{F_n}+s_1}$$ but since $\frac{F_{n+1}}{F_n}$ tends to $\varphi$ for large $n$ and $\frac{F_{n-1}}{F_n}$ tends to $\varphi^{-1}$, we can see that the above will tend towards $$\frac{s_0+\varphi s_1}{\varphi^{-1} s_0 + s_1}$$ which equals $\varphi$, since the denominator multiplied by $\varphi$ is the numerator. So, this establishes that any Fibonacci-like sequence must have the same limiting ratio as the Fibonacci sequence, which is $\varphi$. A note of caution is that if the denominator, $\varphi^{-1} s_0 + s_1$ is zero, (i.e. if $s_1=\frac{-s_0}{\varphi}$) then this doesn't work - indeed, in this case, it must be that $s_n=s_0\cdot (-\varphi)^{-n}$ and the limiting ratio is $\frac{1}{\varphi}$.

A deeper result is to notice that $s_n=\varphi^n$ and $s'_n=(-\varphi)^{-n}$ are both Fibonacci sequences as well, which lead to Binet's formula when you find a linear combination of those two equalling the Fibonacci sequence. Clearly, the exponentially growing $s_n$ term dominators the decaying $s'_n$ term, which is why $\phi$ is the limit of the ratio of successive Fibonacci numbers; if you want to derive this, notice that $\varphi$ is the solution to $$s_n=s_{n-1}+s_{n-2}$$ $$\varphi^n = \varphi^{n-1} + \varphi^{n-2}$$ Or, dividing by $\varphi^{n-2}$ gives $$\varphi^2=\varphi+1$$ which is indeed a property of the golden ratio, and exactly the equation it comes from.

Answer 3

In case of interest, this phenomenon is not restricted to Fibonacci and Lucas numbers, or that law. Even if we stick with linear degree two recurrences, for example $$ \color{magenta}{ x_{n+2} = 4 x_{n+1} - x_n}, $$ the ratio of consecutive numbers in the sequence has a well defined limit, in this case the largest root of $$ \lambda^2 - 4 \lambda + 1 = 0, $$ or $$ 2 + \sqrt 3 \approx 3.73205, $$ at least as long as we start with, say, $x_1 \geq x_0.$ So, take $$ 1, 1, 3, 11, 41, 153, 571, 2131, 7953, 29681, $$ or $$ 1, 2, 7, 26, 97, 362, 1351, 5042, 18817, $$ For the first sequence, there are constants $A,B,$ with $A > 0,$ such that $$ x_n = A \, \left(2 + \sqrt 3 \right)^n + B \, \left(2 - \sqrt 3 \right)^n. $$ For the second sequence, there are (probably different) constants $C,D,$ with $C > 0,$ such that $$ x_n = C \, \left(2 + \sqrt 3 \right)^n + D \, \left(2 - \sqrt 3 \right)^n. $$

For either sequence, a number divided by the previous number in the sequence is approximately $2 + \sqrt 3.$

Answer 4

@frimann bjornsson: Your sequence is $3,4,7,\ldots$, with first index $1$, so $u_1=3$, $u_2=4$, $\ldots$. You can check that $$u_n = (\frac{1+\sqrt{5}}{2})^{n+1} + (\frac{1-\sqrt{5}}{2})^{n+1}$$

This formula allows us find particular terms of the sequence, for instance $$u_{96}=186982561199565069121\\ u_{97}=302544139324403592003\\ u_{98} = 489526700523968661124\\ u_{99} = 792070839848372253127$$

Consider $u_{99} = (\frac{1+\sqrt{5}}{2})^{100} + (\frac{1-\sqrt{5}}{2})^{100}$. If we multiply by $\frac{1+\sqrt{5}}{2}$ we get $(\frac{1+\sqrt{5}}{2})^{101} + (\frac{1-\sqrt{5}}{2})^{100}\cdot \frac{1+\sqrt{5}}{2}$, which is almost $u_{100} = (\frac{1+\sqrt{5}}{2})^{101} + (\frac{1-\sqrt{5}}{2})^{101}$, with a tiny error of $(\frac{1-\sqrt{5}}{2})^{100}\cdot \sqrt{5}$. Some high precision calculation gives:

$$u_{99} \cdot \frac{1+\sqrt{5}}{2} = 792070839848372253127 \cdot \frac{1+\sqrt{5}}{2} = \\ =1281597540372340914251.00000000000000000000282306564641\ldots $$ while $\ \ u_{100} = 1281597540372340914251$

The same thing works in general.

Answer 5

$S_n=\phi^n$ and $S_n=(-\phi)^n$ are two solutions of the Fibonacci recurrence $S_n+S_{n+1}=S_{n+2}$, because $1+\phi=\phi^2$ and $1-\phi^{-1}=\phi^{-2}$.

By linearity, any combination $S_n=a\phi^n+b(-\phi)^{-n}$ is also a solution. You can adjust $a$ and $b$ to match any two initial values. For instance,

$$S_0=3=a\cdot1+b.1,\\S_1=4=a\cdot\phi-b.\phi^{-1},$$ giving $$a=\frac{3\phi^{-1}+4}{\phi+\phi^{-1}},\\b=\frac{3\phi-4}{\phi+\phi^{-1}}.$$ For growing $n$ the powers of $-\phi$ quickly become neglictible (except if $a=0$), and $$S_n\approx a\cdot\phi^n,$$a geometric progression of ratio $\phi$.

$$\begin{align} & S_n & a\phi^n\ \ \ \ \ \ \ \ \\ & 3 & 2.61803398875 \\ & 4 & 4.23606797750 \\ & 7 & 6.85410196625 \\ & 11 & 11.0901699437 \\ & 18 & 17.9442719100 \\ & 29 & 29.0344418537 \\ & 47 & 46.9787137637 \\ & 76 & 76.0131556175 \\ & 123 & 122.991869381 \\ & 199 & 199.005024999 \\ & 322 & 321.996894380 \\ & 521 & 521.001919379 \\ & 843 & 842.998813759 \\ & 1364 & 1364.00073314 \\ & 2207 & 2206.99954690 \\ & 3571 & 3571.00028003 \\ & 5778 & 5777.99982693 \\ & 9349 & 9349.00010696 \\ & 15127 & 15126.9999339 \\ & 24476 & 24476.0000409 \\ \end{align}$$

Answer 6

Let $s_n$ be such a sequence, and suppose the limit exists. Then,

$$ L = \lim_{n \to \infty} \frac{s_n}{s_{n-1}} = \lim_{n \to \infty} \frac{s_{n-1} + s_{n-2}}{s_{n-1}} = 1 + \left( \lim_{n \to \infty} \frac{s_{n-1}}{s_{n-2}} \right)^{-1} = 1 + L^{-1}$$

We see the limit is nonzero and noninfinite, and thus we can simplify to $L^2 - L - 1 = 0$, meaning that either $L = (1 + \sqrt{5})/2$ or $L = (1 - \sqrt{5})/2$.

There is actually a counterexample to your hypothesis! Suppose we define

• $s_0 = 1$
• $s_1 = (1 - \sqrt{5})/2$
• $s_n = s_{n-1} + s_{n-2}$

Then you will find that the limit converges to $(1 - \sqrt{5})/2$.