Determine the (N-1)th fibonacci number from a given extremely large Nth ? [closed]

Hi mathgeeks,

Given an extremely large fibonacci number X, and it's position in the fibonacci sequence N, is there any way to determine the N-1th fibo num, WITHOUT doing the bruteforce dance of counting from 1 upwards?

I've tried attacking the problem by dividing the number by two, and determining the difference between the N-1th, and N-2th, but that would require calculating Fib(n-3)/2, which makes the problem circular.

Also would be interested, if this can be proven not to be possible, thanks

closed as off topic by Todd Trimble♦, Mark Sapir, José Figueroa-O'Farrill, Andrés E. Caicedo, Qiaochu YuanDec 26 '10 at 16:49

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

• Just divide by the golden mean and round to the nearest integer. This gives the correct (n-1)st Fibonacci provided that F_n is greater than 1. – Todd Trimble Dec 26 '10 at 15:34
• @Todd, that's a very similar approach to the one suggested below by J.C. Ottem. – Mariano Suárez-Álvarez Dec 26 '10 at 15:41
• Yes, I see that now. Anyway, I vote to close this question as being not anywhere near research level. – Todd Trimble Dec 26 '10 at 15:42

For large $n$, $\frac{f_{n+1}}{f_n} \approx \phi = 1.618..$. Hence you can get $f_n$ from $f_{n+1}$ by rounding $\frac{f_{n+1}}{\phi}$ to the nearest integer.