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