How can I find an inverse to the Binet formula?

Question

I'm already aware of the Binet formula $\displaystyle F_n = \frac{\varphi^n + \frac{1}{\varphi^n}}{\sqrt{5}}$. I'm attempting to find the inverse of that formula so I can find the position in the sequence of Fibonacci numbers. In fact, at first glance it's relatively easy:

$$ F_n\sqrt{5} = \varphi^n + \frac{1}{\varphi^n}\\ \varphi^nF_n\sqrt{5} = \varphi^{2n} + 1\\ \varphi^{2n} - \varphi^nF_n\sqrt{5}+ 1 = 0\\ \varphi^n = \frac{F_n\sqrt{5}+ \sqrt{5F_n^2 - 4}}{2}\\ n = \log_\varphi\left(\frac{F_n\sqrt{5}+ \sqrt{5F_n^2 - 4}}{2}\right) $$

But this isn't quite correct. The problem is that we must subtract or add 4 depending on whether the Fibonacci number has odd or even position in the sequence (or rather, whether $5F_n^2 - 4$ is a perfect square; admittedly, we could just go by this indicator, but I want to avoid that if at all possible). So the formula is actually:

$$ n = \log_\varphi\left(\frac{F_n\sqrt{5}+ \sqrt{5F_n^2 + 4(-1)^n}}{2}\right) $$

But that doesn't work for me, because n appears in multiple places in the formula, and you'd need to know if it's odd or even to be able to derive it. So if you do the work, you'll see that I'm trying to isolate n in the expression:

$$ \varphi^{2n} - \varphi^nF_n\sqrt{5} = (-1)^n $$

Or alternatively, find an operation that when applied to the numbers 3, 8, 21, 55, 144, etc. gives an even number, and when applied to the numbers 2, 5, 13, 34, 89 gives an odd number.

As a side note, I find it highly unnerving that the almighty quadratic formula fails in this particular case.

Update: I am only interested in solving either of the two problems posed above, not in other ways to find Fibonacci numbers' positions in the sequence.

Answer 1

I think your formula is not Binet's. Binet's formula is $$F_n=\frac{\varphi^n-\frac{1}{(-\varphi)^n}}{\sqrt{5}},$$ which agrees with your formula for odd $n,$ but not for even $n$. In fact, for even $n$ the numbers your formula gives are not even rational.

So the quadratic formula does not fail. It's just that you've applied it to the wrong formula. Unfortunately the quadratic formula cannot be applied to the correct formula since the correct formula does not contain $\varphi^n$ in both terms—one term contains $(-\varphi)^n$ instead—and so your algebra doesn't go through the same way.

Another remark: the formula you are hoping to find must fail for $n=1$ or $2$ since $F_1=F_2=1$ and you can't have two different numbers as the inverse of $1.$

Answer 2

The second term vanishes quite quickly. We have $F_n=\lfloor \frac{\phi^n}{\sqrt{5}}+\frac{1}{2}\rfloor$, where $\lfloor \cdot \rfloor$ denotes the floor function. If the floor weren't there, you could solve for $n$, and if you rounded you would be wrong only for possibly very small $n$.

Update: A quick calculation shows that $n=\left[ \log_\phi \sqrt{5}(F_n-\frac{1}{2}) \right]$ holds for all $n\ge 3$, and fails for $n=1,2$. In this case $[\cdot]$ denotes the rounding function, or $[x]=\lfloor x+\frac{1}{2}\rfloor$.