5
$\begingroup$

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}$)?
  • 0
    @nayrb Yes, exactly.2012-09-06

5 Answers 5

0

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 ϕ}$

6
  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 Aang's answer, this form can be inverted fairly easily.

6

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}}$

2

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$

  • 0
    @ErickWong: Thanks for pointing out.I edited it2012-09-06
2

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$