# Fibonacci nth term

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

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

-
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.

-

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$

-

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$

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

-