Lucas NumbersDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/