Why is the Fibonacci ratio though a decreasing function, it is alternating and decreasing?

Question

I tried to find the ratio of consecutive terms of the Fibonacci series and found that it is a decreasing function and it converges . I tried it though a small code piece in python so that I can have a lot of data points to analyze.

import math

def F(n):
    return ((1+math.sqrt(5))**n-(1-math.sqrt(5))**n)/(2**n*math.sqrt(5))

for i in range(53):
    a = F(i)
    b = F(i+1)

print str(b) + '/' + str(a) + '=>' + str(b/a)

And it gave values which suggested that it is a decreasing function and it converges at around 1.618. But I found that, though it was decreasing, it was not a continuously decreasing function, it in fact increases and decreases alternatively. But overall it was decreasing and converging.

And I tried to plot the values to prove this graphically.

(I expanded the graph a bit by plotting for $n*3$, just to make the view clear)

My doubt is this - What is so special in this series which makes it behave alternating in nature?

I tried to do it for consecutive numbers ratio and found that it was a increasing but not alternating like the Fibonacci ratios.

Thanks

Answer 1

Consider the formula you used for calculating the values: $$F_n = \frac{1}{\sqrt{5}}\left(\phi^n - \psi^n\right)$$ where $\phi=\frac{1}{2}\left(1+\sqrt{5}\right)$ and $\psi=\frac{1}{2}\left(1-\sqrt{5}\right)$.

The ratio of consecutive terms can then be expressed as $$\frac{F_{n+1}}{F_n}=\frac{\phi^{n+1}-\psi^{n+1}}{\phi^n - \psi^n} = \phi + \frac{(\phi-\psi)\psi^n}{\phi^n -\psi^n}$$

There are is a couple of observations we can now make:

• We have $|\phi|>1$ and $|\psi|<1$. Thus, with increasing $n$, the value of $\psi^n$ will get closer and closer to zero, while $\phi^n$ will grow further and further. This already implies the ratio $(F_{n+1}/F_n)$ converges to $\phi$, since the other term converges to zero (its numerator is going to zero and denominator to infinity).
• $\psi<0$, so $\psi^n$ flips its sign whenever we increase $n$ by one. Therefore, the second term oscillates from positives to negatives; making the ratio alternate between being greater than $\phi$ and smaller than $\phi$.

The first observation can be generalized to any sequence which can be expressed as a linear combination of exponentials, the greatest of which has base greater (in absolute value) than 1. The ratio of consecutive terms will converge to this greatest base.

Answer 2

This is not a complete answer to your question, but this is a feature of continued fractions - and the Fibonacci Sequence can be generated in this way.

Amongst other sources try this and this. Hardy and Wright "Introduction to the Theory of Numbers" has a pretty good introduction too.

Answer 3

Instead of approaching the question via continued fractions, one can look at the closed form solution of the recurrence $F_n=F_{n-1}+F_{n-2}$ with initial values $F_0=0$ and $F_1=1$: this is given by the Binet formula

$$F_n=\frac{\varphi^n-\widehat\varphi^n}{\sqrt5}\;,$$

where $\varphi$ and $\widehat\varphi$ are respectively the positive and negative solutions of the quadratic $x^2-x-1=0$,

$$\varphi=\frac{1+\sqrt5}2\approx1.618\quad\text{and}\quad\widehat\varphi=\frac{1-\sqrt5}2\approx-0.681\;.$$

Thus, for the ratio we have

$$\frac{F_{n+1}}{F_n}=\frac{\varphi^{n+1}-\widehat\varphi^{n+1}}{\varphi^n-\widehat\varphi^n}=\varphi+\frac{\varphi\widehat\varphi^n-\widehat\varphi^{n+1}}{\varphi^n-\widehat\varphi^n}=\varphi+\frac{\widehat\varphi^n(\varphi-\widehat\varphi)}{\varphi^n-\widehat\varphi^n}=\varphi+\frac{\widehat\varphi^n\sqrt5}{\varphi^n-\widehat\varphi^n}\;,$$

so that

$$\frac{F_{n+1}}{F_n}-\varphi=\frac{\sqrt5}{\varphi^n-\widehat\varphi^n}\cdot\widehat\varphi^n\;.$$

The factor $\dfrac{\sqrt5}{\varphi^n-\widehat\varphi^n}$ is always positive; $\widehat\varphi^n$ is positive for even $n$ and negative for odd $n$, so

$$\begin{cases}\frac{F_{n+1}}{F_n}>\varphi,&\text{if }n\text{ is even}\\\\ \frac{F_{n+1}}{F_n}<\varphi,&\text{if }n\text{ is odd}\;. \end{cases}$$

This clearly implies the alternating behavior of the ratio:

$$\frac{F_2}{F_1}<\varphi<\frac{F_3}{F_2}>\varphi>\frac{F_4}{F_3}<\varphi<\frac{F_5}{F_4}>\varphi>\frac{F_6}{F_5}<\ldots\;.$$

Answer 4

This is a general property of continued fraction convergents.

Recall that simple infinite or finite continued fractions are represented by

$$[a_0,a_1,a_2,\cdots,a_n]:=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{\cdots+\cfrac{1}{a_n}}}}$$

$$[a_0,a_1,a_2,\cdots]:=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{\cdots}}}=\lim_{n\to\infty}[a_0,\cdots,a_n].$$

If $x=[a_0,\cdots]$ then the rationals $[a_0,\cdots,a_n]$ are called $x$'s partial convergents.

Observe that as $x$ increases, $x^{-1}$ decreases, so $(c+x^{-1})^{-1}$ increases, and so on. Inductively, then, we can conclude that increasing $a_i$ increases $[a_0,\cdots]$ (finite or infinite) if $i$ is even and decreases its value if $i$ is odd. Usually we want the $a_i$ to be natural numbers (except maybe the first) so we get unique representations and can look into arithmetic-diophantine properties of the real number line, but technically we don't need to. So we have

$$[a_0,\cdots,a_n]=[a_0,\cdots,a_{n-1}+a_n^{-1}]\quad \begin{cases}\ge [a_0,\cdots,a_{n-1}] & n~\rm even \\ \le [a_0,\cdots,a_{n-1}] & n~\rm odd.\end{cases}$$

since $a_{n-1}\to a_{n-1}+a_n^{-1}$ amounts to increasing $a_{n-1}$.

Another induction argument shows that each convergent of $x$ is closer to $x$ than the last. In fact we have the following two infinite lists of inequalities:

$$[a_0,a_1]> [a_0,a_1,a_2,a_3]>[a_0,a_1,a_2,a_3,a_4,a_5]>\cdots > x$$

$$x>\cdots\cdots\cdots> [a_0,a_1,a_2,a_3,a_4]>[a_0,a_1,a_2]>[a_0].$$

That is, the values of the partial convergents of $x$ "zig-zag" ever closer to the true value of $x$ from below and above (we are assuming that $x$ has an infinite continued fraction expansion).

It is well-known that the golden ratio $\varphi$ has the continued fraction expansion $[1,1,1,\cdots]$, and furthermore that the partial convergents are the ratio of successive Fibonacci numbers, which is to say that $[\underbrace{1,1,\cdots,1}_n]=F_{n+1}/F_n$. Thus the fact of oscillation follows.

Answer 5

Think of the Fibonacci numbers as starting with $1,1,2,3,5,\dots$. Call these $a_1, a_2.a_3,a_4, a_5,\dots$.

Note that $a_3a_1-a_2^2=1$, $a_4a_2-a_3^2=-1$, and $a_5a_3-a_4^2 =-1$. This nice pattern continues forever. We prove that later, and race to the finish.

So $a_{n+2}a_n-a_{n+1}^2$ alternates forever between positive and negative values.

When $a_{n+2}a_n -a_{n+1}^2$ is positive, we have $a_{n+2}a_n \gt a_{n+1}^2$. Divide both sides by $a_na_{n+1}$. We get $$\frac{a_{n+2}}{a_{n+1}} \gt \frac{a_{n+1}}{a_n}.$$ This says that the 'next" ratio is bigger than the previous ratio.

Similarly, when $a_{n+2}a_n -a_{n+1}^2$ is negative, $$\frac{a_{n+2}}{a_{n+1}} \lt \frac{a_{n+1}}{a_n}.$$ This says that the next ratio is less than the previous ratio.

We have shown that the alternation you observed indeed takes place, if the signs really do alternate. We now show that they do.

Proof of Alternation of Signs: Start from the expression $a_{n+2}a_n -a_{n+1}^2$, replace $a_{n+2}$ by $a_{n+1}+a_n$, and replace one of the $a_{n+1}$ by $a_n+a_{n-1}$. After a small amount of calculation we get $$a_{n+2}a_n -a_{n+1}^2=-\left(a_{n+1}a_{n-1}-a_n^2\right),$$ which shows that the alternation of signs occurs.

The fact that $a_{n+2}a_n-a_{n+1}^2$ has absolute value $1$ can then be used to prove convergence. For note that it says that $$\left|\frac{a_{n+2}}{a_{n+1}}-\frac{a_{n+1}}{a_n}\right| =\frac{1}{a_na_{n+1}}.$$ Thus the absolute value of the difference of the ratios is shrinking rapidly.

Answer 6

So here's a nice explanation of why the ratio is what it is. Note, this isn't yet a satisfactory explanation of why it converges in the first place, but it's a nice starting point.

Suppose that there's some number $L$ so that $\dfrac{F_{n}}{F_{n-1}}\to L$ as $n\to\infty$. We note that at any $n$, we have $$ F_n=F_{n-1}+F_{n-2} $$ Dividing through by $F_{n-1}$, we get that $$ \frac{F_n}{F_{n-1}}=1+\frac{F_{n-2}}{F_{n-1}} $$ Which means that whatever our limit is, it should obey $$ L = 1+\frac1L $$ Rearranging, this gives us $L^2-L+1=0$, Which has the solution $$ L=\frac{1 \pm \sqrt 5}{2} $$ Since only the positive solution makes sense for us, we find that the limit that this sequence approaches (if it's anything) should be $L=\frac12(1+\sqrt 5)\approx 1.618$ (also known as the golden ratio).

Answer 7

There is nothing really special of the Fibonacci series, one can construct a whole class of series that wobble like this, from the iteration $t_{n+1}=c\cdot t_n + t_{n-1}$.

A classical example is the iterations that produce the octagonal series, which equates to $c=2$ and converges on the alternating ratio $1+\sqrt{2}=2.414213456238$.

       1      1         1,000000           a        b
       2      3         1.500000           c=a+b    d=a+c
       5      7         1.400000
      12     17         1.416666
      29     41         1.413793
      70     90         1.414285        
   

The main reason that this happens is that the approximation is of the form $a^n c + b^n d$, where variously $b$ abd $d$ might be negative, with $b<1$. What one gets is an approximation $\frac{a^{n+1}c+e}{a^nc-e}$. which is slightly larger, and then $\frac{a^{n+1}c-e}{a^nc+e}$ which is slightly smaller.

In the Fibonacci series, we have $b=-0.61803398875, d=-1/\sqrt{5}$, in the series above, the value of $b=\sqrt{2}-1=-0.41421356$ suffices to cause this alternation.

Answer 8

Let $F_i$ be the $i$-th Fibonacci number. Put $F_i$ people at one table, and deliver $F_{i-1}$ pizzas to them. Put $F_{i+1}$ people at a second table and deliver $F_i$ pizzas to them. At the first table, there are $F_{i-1}/F_i$ pizzas per person, and at the second table there are $F_i/F_{i+1}$ pizzas per person.

Now have everyone at the first table move to the second table, and bring their pizzas along. In total, there are $F_i + F_{i+1} = F_{i+2}$ people and $F_{i-1} + F_i = F_{i+1}$ pizzas, so we have $F_{i+1}/F_{i+2}$ pizzas per person. If there were more pizzas per person at the first table than at the second (in other words, if $F_{i-1}/F_i > F_i/F_{i+1}$), then bringing over the people from the first table increased the number of pizzas per person at the second table. In other words, $F_{i+1}/F_{i+2} > F_i/F_{i+1}$. If there were more pizzas per person at the second table ($F_{i-1}/F_i < F_i/F_{i+1}$), then bringing over the people from the first table decreased the number of pizzas per person, and $F_{i+1}/F_{i+2} < F_i/F_{i+1}$. This shows the oscillation. Note that either way, $F_{i+1}/F_{i+2}$ sits in between $F_{i-1}/F_i$ and $F_i/F_{i+1}$. The sequence of ratios converges by the alternating series test.

I phrased this in terms of ratios smaller than $1$ to avoid the appearance of gluttony, but obviously you can do the same thing with ratios greater than $1$ ($F_{i+1}/F_i$), or just take reciprocals.