Lucas Numbers

Date: 11/22/96 at 21:04:45
From: Daeman Mc Leod
Subject: Lucas Numbers

Hi;

This is really a simple questiion, just out of interest.  I would 
like to know why the number 2 is not a Lucas number.  I have looked
in books but have been unable to find the answer.

I hope you can help!

Date: 11/24/96 at 20:46:09
From: Doctor Pete
Subject: Re: Lucas Numbers

Well, I can give you two different explanations, depending on how one
defines Lucas numbers, and in general, sequences of numbers generated 
by recursion relations.

If you've heard of Lucas numbers, undoubtedly you've also heard of 
Fibonacci numbers.  They are generated by the following recursion 
relations:

     F[n] = F[n-1] + F[n-2], F[0] = 0, F[1] = 1
     L[n] = L[n-1] + L[n-2], L[0] = 2, L[1] = 1

So we make a short table of values (notice that F[n-1] + F[n+1] = 
L[n]):

     n  |  0   1   2   3   4   5   6   7
    ====+================================
    F[n]|  0   1   1   2   3   5   8  13
    L[n]|  2   1   3   4   7  11  18  29

Notice that 2 can be considered a Lucas number, just not one that
corresponds to a positive integer value of n. It's really up to how 
you want to start counting. Lots of mathematicians consider counting 
to start at 0, not 1. But that's not really the issue here, because 
you could have simply started with F[0] = 1, F[1] = 1, and L[1] = 1, 
L[2] = 3. In shifting the table over to the left, we seem to have rid 
ourselves of the problem. But not really, because the recursion 
relation gives us a way to go *backwards* in the list. One can ask, 
"What's F[-1]?" And it doesn't take much to see that F[-1] = 1, since 
F[-1] + F[0] = F[1]. Continuing in the other direction, we see that:

     n  |  0   -1   -2   -3   -4   -5
    ====+=============================
    F[n]|  0    1   -1    2   -3    5
    L[n]|  2   -1    3   -4    7  -11

and it comes as no surprise that we should get terms of alternating 
sign, and furthermore, they "mirror" the positive terms in their size.  
So you can't really avoid the fact that 2 is in some sense a Lucas 
number; the bottom line is that it is inherent in how you pick the 
initial conditions, namely L[0] and L[1] (or L[1] and L[2], if you 
prefer to count from 1).

Loosely speaking, if you had picked F[1] = F[2] = 1, then tried to 
create a new sequence by picking L[1] = 1, L[2] = 2, then you'd fail, 
because F[3] = 2, and we would get L[n] = F[n+1].  So in a way, one 
would have to pick L[2] = 3 to get a new sequence.

Now, this is all fine and well, but you can look at the entire thing 
from a different perspective:  Define the Lucas numbers L[n] to be the 
function

     L[n] = P^n + Q^n,

where P = (1+Sqrt[5])/2, and Q = (1-Sqrt[5])/2.  (P^n means P raised 
to the power of n, and similarly, Q^n means Q raised to the power of 
n.)  At first it does not seem clear that P^n + Q^n would give integer 
values for all n, considering that neither P nor Q are integers 
themselves; but a bit of thought should convince you that this 
definition gives an integer for each integer value of n.  Furthermore, 
n = 0 gives L[0] = P^0 + Q^0 = 1 + 1 = 2.

Curiously, this seems to have dispensed of any notion of "initial
condition," not to mention any sort of recursion whatsoever!  It gives 
L[n] as a direct function of n.  Is there a similar formula for F[n]?  
Indeed there is, and ironically enough, it is called "Lucas' formula 
for the Fibonacci numbers."  It is:

     F[n] = (P^n - Q^n)/Sqrt[5],

where P and Q are the same numbers defined above.  This again gives 
integer values for all n, and clearly F[0] = 0.  What has happened 
here?  What is the relation between the recursive formulas and the 
non-recursive ones?  These are questions that have interesting and 
deep answers, which are too long to be dealt with here (as I've 
already written quite a bit), but a hint of this can be found at:

  http://www.ugcs.caltech.edu/~peterw/studies/fibonacci/   

But you will note that either way you define Lucas numbers, 2 is 
indeed a Lucas number.  While it appears that I have given two 
separate reasons, they are in fact intimately related.

I apologize for the lengthy response, but I felt that I needed to 
explain to some extent what happens behind the scenes (considering the 
answer to your question involved explaining why 2 *is* a Lucas 
number).  Hope it cleared things up.

-Doctor Pete,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/