The Origin of Lucas Numbers

Date: 10/08/98 at 14:56:29
From: DJ smith
Subject: Lucas Numbers

I need help with Lucas Numbers - how they were created, why they were 
created.

Thank you, 
DJ

Date: 10/08/98 at 16:02:37
From: Doctor Rob
Subject: Re: Lucas Numbers

DJ, 

Lucas Numbers, or the Lucas Sequence, were discoverd by Edouard Lucas, 
a French mathematician, in the 1870s. He was studying what are called
Linear Recursive Sequences. These are sequences of numbers gotten by 
means of a recursion, that is, a formula relating the value of one 
number in a sequence to earlier ones. A linear recursion is one in 
which the earlier numbers all appear in separate terms, to the first 
power, times constants. The classic example is the Fibonacci Sequence:

   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

with the recursion:

   F(n+1) = F(n) + F(n-1)

and initial conditions F(0) = 0, F(1) = 1. The *span* or *degree* 
of the recursion is the difference between the highest and lowest 
subscripts in the recursion ([n+1]-[n-1] = 2 in the Fibonacci 
recursion). Lucas discovered that if the degree is d, there are 
always d and at most d "independent" sequences satisfying the same 
recursion (with different starting values).

In the case where the degree is 2, like the Fibonacci numbers, the
recursion can be written as:

   U(n+1) = A*U(n) + B*U(n-1)

There are two independent sequences (that is, one is not a multiple of 
the other) satisfying this. You can always pick one such that U(0) = 0 
and U(1) = 1, and you can always pick a second one such that the 
U(0) = 2 and U(1) = A. Every sequence satisfying the recursion, even 
if its terms are not whole numbers, can be shown to be a constant times 
the the one plus a constant times the other.

The second sequence which is independent of the Fibonacci sequence and
starts 2, 1, ... is now called the Lucas sequence after Edouard Lucas.
Why choose 2, 1, ... for the start? It is probably because of the Binet 
formulas for the Fibonacci and Lucas numbers:

   F(n) = (a^n-b^n)/(a-b)
   L(n) = a^n + b^n

where n >= 0, a = (1+sqrt[5])/2, and b = (1-sqrt[5])/2. The a and b are 
the two solutions to x^2 = x + 1. The fact that the coefficients of a^n 
and b^n are equal in magnitude and opposite in sign in the first 
formula, and equal in magnitude and sign in the second, is probably why 
this is the simplest and easiest second, independent sequence to take. 
The first few terms of the Lucas sequence look like this:

   2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...

As an example of the above, suppose we had a start of S(0) = 3, 
S(1) = 2, and the same recursion:

   S(n+1) = S(n) + S(n-1)

Then the sequence would look like:

   3, 2, 5, 7, 12, 19, 31, 50, 81, ...

Then we can easily find that:

   S(n) = (1/2)*F(n) + (3/2)*L(n)

Check this yourself!

Furthermore, there are many beautiful and intriguing identities that 
F(n) and L(n) satisfy, such as, for all n:

   F(2*n) = F(n)*L(n)
   F(n+1) = [L(n)+F(n)]/2
   L(n+1) = [L(n)+5*F(n)]/2
     L(n) = F(n+1) + F(n-1)
   F(n-1) = [L(n+1)+L(n-1)]/5

If we had chosen a different second independent sequence, these 
identities would have been more complicated.

Here is a web page with lots about Lucas numbers:

 http://www.ee.surrey.ac.uk/Personal/R.Knott/Fibonacci/lucasNbs.html   

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/