Generalised 'Fibonacci' Series and Phi

Date: 02/10/2002 at 11:47:18
From: Stuart Donnan
Subject: Generalised 'Fibonacci' series and phi

I have searched but I can't find an answer to this.

I have shown with a spreadsheet that a Fibonacci-style series that 
starts with any two numbers at all, and adds successive items, 
produces a ratio of successive items that converges to phi in about 
the same number of terms as for the 1 1 2 3 5 etc. basic Fibonacci 
series.  I can't find reference to this - maybe I don't know how to 
look - surely this is well known?  Is it - and is it provable?

Thanks.

Date: 02/11/2002 at 07:01:52
From: Doctor Floor
Subject: Re: Generalised 'Fibonacci' series and phi

Hi, Stuart,

Thanks for your question.

To prove your conjecture we will delve into formulas of generalized 
Fibonacci sequences (sequences satisfying X(n) = X(n-1) + X(n-2) ). 
Let's first investigate two very special members of the family of 
generalized Fibonacci sequences, those of the form

   X(1)=g=g^1, X(2)=g^2, X(3)=g^3, ..., X(n)=g^n  [g nonzero]

Since X(n)=X(n-1)+X(n-2), we must have:

   g^n = g^(n-1) + g(n-2)
   g^n - g^(n-1) - g(n-2) = 0
   g^(n-2) * (g^2 - g - 1) = 0  
   g^2 - g - 1 = 0   [we can divide by g^(n-2) becuase g is nonzero]

So g must be one of the roots of g^2 - g - 1 = 0, so it must be one of 
the following numbers:

   Phi = (1+SQRT(5))/2  (the Golden Ratio)
   1-Phi = (1-SQRT(5))/2

So we have two very special generalized Fibonacci sequences:

   Phi^1, Phi^2, Phi^3, ..., Phi^n, ...
   (1-Phi)^1, (1-Phi)^2, ..., (1-Phi)^n, ...

I leave it for you to check that, when you have two generalized 
Fibonacci sequences A(n) and B(n), and two numbers a and b, then 
a*A(n) + b*B(n) is a generalized Fibonacci sequence. 

In fact, all generalized Fibonacci sequences can be calculated in 
this way from Phi^n and (1-Phi)^n. This can be seen from the fact 
that any two initial terms can be created by some a and b from two 
(independent) pairs of initial terms from A(n) and B(n), and thus 
also from Phi^n and (1-Phi)^n.

So each generalized Fibonacci sequences can be written as

  X(n) = a*Phi^n + b*(1-Phi)^n.

Now your statement follows for all sequences for which a<>0, when we 
realize that |1-Phi|<1, so that (1-Phi)^n --> 0 for n --> infinity.

So we see that there are exceptions: sequences b*(1-Phi)^n.

If you have more questions, just write back.

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/   

Date: 02/12/2002 at 04:31:46
From: Stuart Donnan
Subject: Generalised 

Dr. Floor,

Many thanks for your clear response.  I did keep looking, and thought 
that this answer by Dr. Rob in the Dr. Math archives was helpful:

   The Golden Ratio
   http://mathforum.org/dr.math/problems/miller2.23.98.html   

Generalising F(n+1) = F(n) + F(n-1) (without requiring F(0)=0, F(1)=1 
etc.) and dividing both sides by F(n) and rearranging etc.

Dr. Rob concludes, 'if the ratio converges to anything, it converges 
to the Golden Ratio'.  This is neat but not quite the same sort of 
'proof' as yours.

I'm surprised that there isn't more to be found (at least easily) 
about 'generalised' Fibonacci series, but there you go.

Thanks again.
Stuart