Approximating Fibonacci numbers

Question

Is there a relatively quick and relatively accurate way of computing $F(10000)$, the $10000$th Fibonacci number, without the use of a computer?

I considered the general solution to their recurrence, but computing $\phi^n$ where $\phi$ satisfies $\phi = 1 + \phi^{-1}, \space \phi > 1$ doesn't seem helpful as its difficult to say when its ok to start forgetting about the terms proportional to $\phi^{-k}$ for some positive integer $k$.

The only thing that seemed slightly handy is the fact that $\frac{F(n+1)}{F(n)} \to \phi$, so, hoping $n=10000$ is large enough for a decent approximation, we can say $F(10000) \approx \phi F(9999) \approx \phi^2 F(9998) \approx \dots$, but again its difficult to say when this approximation becomes very inaccurate and will inevitably have us need to calculate some decently large Fibonacci by hand at some point, e.g. $F(100)$.

Answer 1

It's a big number, so you're going to have to do a lot of computation regardless. Binet's formula states $$F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$$ Note that $\left|\frac{1-\sqrt{5}}{2}\right|<1$, so we can say that $F_n\approx\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n$ and then round the RHS to the nearest integer. You could compute the RHS by repeated squaring to get various powers of $\phi^{2^n}$ and then multiplying, but this is arithmetic with an irrational number which is tough. You would need to predict how many decimal digits to keep along the way so that you don't mess up. The good thing is powers of $\phi$ approach integers (in particular, the lucas numbers) fairly quickly for the same reason so eventually you could probably switch to an integer and be fine to some degree.

An alternative method, and this is probably what a computer algorithm might use is the fact that $$\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}=\begin{pmatrix}1&1\\1&0\end{pmatrix}^n$$ If $A=\begin{pmatrix}1&1\\1&0\end{pmatrix}$, then we can compute $A^{10000}$ by computing $A,A^2,A^4,\ldots,A^{2^{13}}$ and then make use of the binary expansion of $10000$.

Answer 2

The ten thousand fibonacci number has over $2000$ digits. There is no good way of working with numbers this large without a computer.

Regardless, have you tried computing the first few fibonacci numbers and comparing them to $\frac{\phi^n}{\sqrt{5}}$ evaluated at the first few naturals?

If you did that, you would see that the error begins small enough that it vanishes with rounding, and quickly tends towards $0$. Just use the aforementioned geometric series.