Dear Uncle Colin,

I’m aware of Binet’s formula for finding the $n$th Fibonacci number, $F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}$, and wondered if there was an inverse version - to find $n$ given a Fibonacci number.

-- Fibonacci Explicit Inverse, Getting Extremely Nervous But Am Understanding More

Hi, FEIGENBAUM, and thank you for your message!

I have two answers to this: one a ‘good enough for engineers’ sort of answer, and one a ‘doing it properly’ one.

Good enough for engineers

The $(-\phi)^{-n}$ term in Binet’s formula is generally small. For $n=1$, its contribution to the sum is less than 0.3, and it drops quite rapidly from there. This suggests simply ignoring that element of the formula and stating that $F_n \approx \frac{\phi^n}{\sqrt{5}}$, so $n \approx \log_\phi \left( \sqrt{5} F_n \right)$.

For example, if your Fibonacci number was 144, this would evaluate to 11.99998, roughly, which gives a good suggestion that $n$ might be 12.

A proper answer

As you know, FEIGENBAUM, small disturbances can often lead to chaotic effects! As mathematicians, saying 11.99998 is practically 12 simply isn’t good enough.

Instead, let’s get all quadratic. Start by making the substitution $z = \phi^n$ and multiplying by $\sqrt{5}$ to get $F_n \sqrt{5} = z - \frac{(-1)^n}{z}$.

Multiplying by $z$ and rearranging gives $z^2 - F_n \sqrt{5} z - (-1)^n$ - which we can solve, as long as we take into account the two possible values for the final term.

We get $z = \frac{F_n \sqrt{5} \pm \sqrt{ 5F_n^2 - 4(-1)^n}}{2}$. Only the positive branch makes sense in context, so our almost-explicit formula is $z = \frac{F_n \sqrt{5} + \sqrt{ 5F_n^2 \pm 4}}{2}$. We’ll then need to take the logarithm of this (base $\phi$) to determine $n$.

If $F_n = 144$ again, we have $z = \frac{ 144 \sqrt{5} + \sqrt{5\times 20736 \pm 4}}{2}$. Let’s tidy that up before the Mathematical Ninja shows up: $z = 72 \sqrt{5} + \sqrt{ 25920 \pm 1}$.

Of course, everyone knows that $\sqrt{25921}=161$ - after all, it’s 321 more than 25,600 - so that seems the most likely way to go.

Then we have $\phi^n = 72\sqrt{5} + 161$; taking logarithms base $\phi$ of both sides gives $n = 12$ exactly, as required.

Hope that helps!

-- Uncle Colin