Friday, 6 July 2018

Derivation of nth Term of a Lucas Sequence - Fibonacci Numbers and the Golden Ratio

Who am I?  Index of Blogs

I present a full derivation of the general term Gn of a Lucas sequence, and discuss the cases of the Fibonacci and Lucas numbers.  The Golden Ratio Φ (Greek letter Phi) enters in the discussion naturally and is an integral part of the derivation. 

The unique properties of Fibonacci Numbers and the Golden Ratio have captivated scientists, artists, architects and others over many centuries.  They are abundantly found in nature - particularly in the arrangement of petals and branches in plants.  There are many places where their properties are described but it is difficult to find a derivation of the general term without going to mathematical journals where the subject is treated formally and also much background in mathematics is assumed.  
The presentation here is suitable for someone with a knowledge of school level mathematics.      

I define the Lucas sequence as follows:   A Lucas Sequence is a series of numbers where the nth term is formed by adding the two terms immediately preceding it. 
The series starts from n = 0 and is represented by the recurrence relation:

                            Gn+1 = Gn + Gn-1    for n ≥ 1          ...  eq. 1 

The first two terms, G0 and G1, uniquely determine the rest of the elements of the series.  For example, the choice  
G0 = 0 and G1 = 1, gives the Fibonacci numbers 0,1,1,2,3,5,8,13,21, ...    while 
G0 = 2 and G1 = 1, gives the Lucas numbers 2,1,3,4,7,11,18,29, ...
In order to find the nth term, we define a generating function G(x) as a power series in x whose coefficients are the elements of the Lucas sequence.

[Click on a slide to see full page image, press Esc to return to text]

Equation 6 defines the generating function of the Lucas sequence with the first two terms equal to G0 and G1.  
The next step is to expand G(x) in a power series in x.  This is achieved in the following slides:  

Fibonacci and Lucas numbers:  These number series are formed for particular choices of the first two terms 
G0 = 0 and G1 = 1, gives the Fibonacci numbers
 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,  ...

G0 = 2 and G1 = 1, gives the Lucas numbers
 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 143, 219, 362,  ...

The full expression for the nth term is given in equation 13 and with the particular choices allows us to write: 
Equations 14 and 15 are expressions for general F and L series while equation 16 gives the approximation for large values of n.
We notice the very close similarity of the Fibonacci and Lucas series and their intimate relationship with the Golden ratio.

Extensions:  The recurrence relation in eq. 1 that we had used is
           Gn+1 = Gn + Gn-1    for n ≥ 1          ...  eq. 1

Many different sequences may be constructed by modifying eq. 1.  A general form might be as follows:

           Gn+1 = P Gn - Q Gn-1    for n ≥ 1          ...  eq. 17 

It is also possible to have a term equal to the sum of, say, preceding three terms (the tribonacci series) etc. 

One of the more intriguing extensions is the Random Fibonacci Sequence where P and Q in eq.17 are allowed to take values of +1 or -1 in a  random fashion with probability 0.5. Divakar Vishwanath found that for large n, the sequence increases as (1.13198824...)n with a probability of 1.- a completely counterintutive result.  The number 1.13198824 has been named as the Vishwanath number.  

Final Word:  In this blog I have set out the background to the development of Fibonacci numbers and establish their close relationship to the golden ratio.  I feel the derivation of the general term has a great heuristic value as the method detailed here for the calculation of the generating function for a given recurrence relation may be applied to other cases as well.  I was guided by the book 'Generatingfunctionology' by Herbert S Wilf.

In my next blog, I wish to explore the wonderful worlds of Fibonacci numbers and the Golden Ratio.  These two characters prop up in completely different situations generating surprise and a delightful feeling.  
Congratulations if you are reading this sentence - well done.

Post a Comment