Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It is known that the nth term of the Fibonacci sequence can be found by the formula:

$F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}$,

where $\phi$ is the golden ratio (1.618...).

  1. Would this be the best formula to generate large terms of the sequence (eg. $n = 10^{15}$)?
  2. How many decimal places of $\phi$ should be known to generate such a large term?
  3. How can this formula be reversed (ie. finding $F_n^{-1}$)?
share|improve this question
    
What do you mean finding $F_n^{-1}$? You mean, given an Fib number $F_n$, find $n$? –  nayrb Sep 6 '12 at 13:52
    
@nayrb Yes, exactly. –  Khaled Sep 6 '12 at 13:55

5 Answers 5

up vote 5 down vote accepted

For part (3), $F_1=F_2=1$ so you cannot hope for an inversion formula which works for all $n$. For large $n$, however, the term in $\phi^{-n}$ becomes very small and $F_n$ is the nearest integer to $\frac {\phi^n} {\sqrt 5}$ and it is very nearly true that$$n=\frac{\log {(F_n\sqrt 5)}}{\log {\phi}}$$

share|improve this answer
  1. For even modestly large $n$, this is not a very good way to generate exact values of $F_n$. Why use floating-point arithmetic when you can just exponentiate $\left(\begin{array}{cc}1&1\\1&0\end{array}\right)$ at least as quickly? It is only useful for quickly estimating the first few digits of $F_n$.

  2. It is not practical to compute exact values of $F_n$ when $n=10^{15}$. This is a number with 200 trillion decimal digits! You'll need at least that many digits of precision in $\phi$, which is just silly.

  3. If you see Avatar's answer, this form can be inverted fairly easily.

share|improve this answer

For the accuracy of $\phi$, as $F_n \approx \frac {\phi^n}{\sqrt 5}$, the fractional error in $F_n$ is the same as your fractional error in $\phi^n$. If instead of $\phi^n$ you have $(\phi(1+\epsilon))^n$ the fractional error is $(1+\epsilon)^n \approx 1+n\epsilon$. If you want $F_n$ to be exact, you need $\frac {n\epsilon}{\phi^n}\lt 1$ or $\epsilon \lt \frac {\phi^n}n$

share|improve this answer

For part $(1)$, Since $\frac{|\phi|^n}{\sqrt 5}\lt \frac{1}{2}$ $$F_n=\lfloor \frac{\phi^n}{\sqrt 5}+\frac{1}{2}\rfloor$$ as where $\lfloor . \rfloor $ represents the greatest integer function

For part $(3)$, For even $n$,$$F_n=\frac{\phi^n-\frac{1}{\phi^n}}{\sqrt 5}=\frac{\phi^{2n}-1}{\phi^n\sqrt 5}$$ $$\implies (\phi^n)^2-(\sqrt 5 F_n) (\phi^n)-1=0$$.

This is quadratic equation in $\phi^n$ solving which we get,

$$\phi^n=\frac{\sqrt 5F_n+\sqrt{5F_n^2+4}}{2}$$ (negative root discarded) $$\implies n=\log_\phi \frac{\sqrt 5F_n+\sqrt{5F_n^2+4}}{2}=\frac{\ln (\frac{\sqrt 5F_n+\sqrt{5F_n^2+4}}{2})}{\ln \phi}$$

As you can see that for large $F_n$, $\sqrt{5F_n^2+4}\approx\sqrt 5 F_n$ which gives $$n\approx\frac{\ln \sqrt 5F_n}{\ln \phi}$$ for large $F_n$

For odd $n$, similar computations follow which give

$$n=\frac{\ln (\frac{\sqrt 5F_n+\sqrt{5F_n^2-4}}{2})}{\ln \phi}$$

But since you don't know whether $n$ is even or odd,

my suggestion is to compute both expressions (for even one as well as odd one) and check which $n$ fits best.

For large $F_n$, those expression would yield same $n$, so no need to worry for large $F_n$

share|improve this answer
1  
I think you have accidentally assumed $n$ is even: $(-\phi)^n = \phi^n$? –  Erick Wong Sep 6 '12 at 14:18
    
@ErickWong: Thanks for pointing out.I edited it –  Aang Sep 6 '12 at 14:27

If you are computing this with a programming language the accuracy will depend on how many decimal digits you have for $\phi$, a better solution is manipulating the original formula $\phi = \frac{1+\sqrt5}2$ while keeping it as it is until expanding it in the last computation..

This is the inverse function: $\frac{\log\left(\frac12\left(\sqrt 5 x - \sqrt{4 + 5 x^2}\right)\right)}{\log ϕ}$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.