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}$)?
$\endgroup$
  • $\begingroup$ What do you mean finding $F_n^{-1}$? You mean, given an Fib number $F_n$, find $n$? $\endgroup$ – abnry Sep 6 '12 at 13:52
  • $\begingroup$ @nayrb Yes, exactly. $\endgroup$ – Khaled Sep 6 '12 at 13:55
6
$\begingroup$

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

$\endgroup$
6
$\begingroup$
  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.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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$

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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