Fibonacci or Lucas Number

Date: 02/19/2003 at 17:19:47
From: Alondra
Subject: Fibonacci or Lucas number

How do I know that any number x is a Fibonacci or Lucas number?

For example, how can I know that 14930352 is a Fibonacci number 
without doing the whole sequence? Is there any way, just like I know 
that 113 is a prime number? Has anyone found that way? 

Also, my Math Fair group really wants to do a project about the 
relation between Fibonacci and Lucas numbers. We've placed both 
sequences on the Spirals of Ulam, and many other different things, and 
we even found a way to find the constant in both numbers using a 
formula, without having to complete the instructions of the Ulam, but 
we get stuck there. I was wondering if there's an incomplete work we 
could continue, or something like that. 

Thank you.

Date: 02/20/2003 at 03:50:48
From: Doctor Floor
Subject: Re: Fibonacci or Lucas number

Hi, Alondra,

Thanks for your question.

In the Dr. Math archives you can find direct formulas for the 
Fibonacci and Lucas sequences:

   A Fibonacci and Lucas Number Relation
   http://mathforum.org/library/drmath/view/52699.html 

With    

   P = (1+SQRT(5))/2  (a.k.a. the Golden Ratio)
   Q = (1-SQRT(5))/2

these formulas are

   F(n) = (P^n - Q^n)/SQRT(5)
   L(n) = P^n + Q^n

Now the absolute value |Q^n|<0.5 for n>1. This means that for n>2 you 
can in both formulas remove Q^n and use rounding instead:

   F(n) = round(P^n/SQRT(5))
   L(n) = round(P^n)

With this, it is easy to find a possible value of n using logarithms. 
Let's take your example: you want to know whether there is an n for 
which F(n)=14930352. We find that 

   log(sqrt(5)*14930352)/log(P)

is approximately equal to 36. So 14930352 might be F(36). We check by 
calculating round(P^36/sqrt(5)) and indeed this is equal to 14930352.

I think this is the quickest way of checking.

If you have more questions, just write back.

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/