Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Fibonacci Sequence/Golden Ratio
High School Number Theory
High School Sequences, Series