# How is the Binet's formula for Fibonacci reversed in order to find the index for a given Fibonacci number?

a question about the Fibonacci sequence:

$$F_n =\frac{\phi^n-(-\frac{1}{\phi})^n}{\sqrt{5}}$$

This is the Binet's formula for the nth Fibonacci number. if I reverse it I can get:

$$(\phi^n)^2-F_n\sqrt{5}(\phi^n)-(-1)^n = 0$$

This equation can be solved using the quadratic formula for:

$$x^2 - bx - 1 = 0$$

And then you get:

$$x_1, x_2 = \frac{F_n\sqrt{5}\pm\sqrt{5F_n^2\pm 4}}{2}$$

So I can guess that $\phi^n$ is either $x_1$ or $x_2$. But how can I prove that $\phi^n$ is actually $$\frac{F_n\sqrt{5}+\sqrt{5F_n^2\pm 4}}{2}$$

With a plus and not a minus after $F_n\sqrt{5}$?

• For the case $\;5F_n^2+4\;$ it follows from $\;F_n\;$ being positive. – Timbuc Nov 14 '14 at 22:18

First, I assume $n$ is nonnegative. For all but the smallest of $n$, we can see this easily with the observation that $4$ is extremely tiny compared to $F_n$, and so

$$\sqrt{5 F_n^2 \pm 4} \approx F_n \sqrt{5}$$

Taking the plus sign would give

$$\phi^n \approx F_n \sqrt{5}$$

and the minus sign would give something comparatively very close to zero. We can use a differential approximation to get a more precise estimate:

$$\phi^n \approx \mp \frac{1}{F_n \sqrt{5}}$$

We also need to know that $|-1/\phi| < 1$, so that $(-1 / \phi)^n \approx 0$, so that Binet's formula tells us

$$F_n \approx \frac{\phi^n}{\sqrt{5}}$$

and so, the plus sign gives the right estimate.

If we consider negative $n$, the same argument says we want to pick the sign that makes things cancel out.

• Just one question: You say $\phi \approx \mp\frac{1}{F_n\sqrt{5}}$. But how is it possible since $\phi$ itself is positive and the nth power of it will be always positive for all n??? – user3019105 Nov 15 '14 at 17:35
• @user: It's not! If the minus sign were correct, then $\phi^n$ would be nearly that; thus we conclude that the minus sign gives the wrong answer. – user14972 Nov 16 '14 at 0:14
• So you are saying that $\phi \approx (\frac{1}{F_n\sqrt{5}})^-$ or $\phi \approx (\frac{1}{F_n\sqrt{5}})^+$, like when you estimate the limit of a function, right? – user3019105 Nov 16 '14 at 8:59

Since the Fibonacci numbers contain the sequence $0,1,1,2,3,5 \dots$ with two successive $1$'s most ways they are determined, there is no way of doing a perfect reversal, because the value $1$ gives two possible results.

• Just assume $n>1$. – egreg Nov 14 '14 at 23:08
• @egreg Indeed, but it needs to be assumed. Logarithms give a good enough approximation for most positive values. – Mark Bennet Nov 14 '14 at 23:15