Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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. enter image description here

(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

share|improve this question
    
Yes , I have used it here .Is there anything wrong .Sorry. If wrong please correct me . –  Harish Kayarohanam Jul 10 '13 at 19:51
2  
This is correct. An explanation can be given by studying Binet's formula or from the theory of convergents of a continued fraction. –  Jyrki Lahtonen Jul 10 '13 at 19:54
    
If so please enlighten me on this .And please explain it based on the ratios (just by numbers) and why these ratio's are so . –  Harish Kayarohanam Jul 10 '13 at 19:59
1  
I'm confused here– is the question "why does the series alternate?", "why does the series converge?", or both? –  Omnomnomnom Jul 10 '13 at 20:04
2  
"it should be surely decreasing as it has larger numbers in denominators" - by that logic, it should surely be increasing as it has increasingly large numbers in the numerator too. –  blue Jul 10 '13 at 20:19

7 Answers 7

up vote 5 down vote accepted

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\;.$$

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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).

share|improve this answer

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.

share|improve this answer

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 fibonnacci 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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