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.

  • $\begingroup$ please update your title and the text of your question. As written it suggests that you are seeking an inverse to the Binet formula. $\endgroup$ – vadim123 Apr 28 '13 at 1:35
  • $\begingroup$ Closely related: math.stackexchange.com/questions/191920/fibonacci-nth-term $\endgroup$ – Erick Wong Apr 28 '13 at 2:17
  • $\begingroup$ None of those answers gives an exact inverse. And I do believe one is possible, because the Binet formula isn't perfect; if you put in 0 you get $\frac{2\sqrt{5}}{5}$. $\endgroup$ – Linus Apr 28 '13 at 5:19
  • $\begingroup$ And if you put in 2 you get $\frac{75 + 282\sqrt{5}}{620}$, not quite the same thing as 1. $\endgroup$ – Linus Apr 28 '13 at 5:32
  • 1
    $\begingroup$ @Linus: Or, you could have the wrong formula. $\endgroup$ – Hurkyl Apr 28 '13 at 9:10

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

  • $\begingroup$ Thank you. This is exactly the answer I wanted: why it can't be done, or how to derive it if it can be done. Actually, in theory one could apply the quadratic formula to the correct formula, but that would require knowledge of whether n is odd or even (i.e. $x^2(-x)^2 = x^4$ but $x^3(-x)^3 = -x^6$, and I asked this question to avoid knowing that $\endgroup$ – Linus Apr 29 '13 at 0:16
  • $\begingroup$ Now, is there such an operation as the one I describe, and/or is it possible to solve the final equation I give? $\endgroup$ – Linus Apr 29 '13 at 3:05
  • $\begingroup$ Can you explain what it is about operations that involve rounding that you find objectionable? I believe that any solution to your problem will either involve rounding, or will sneak rounding in through the back door. The answer is going to be an integer, so it should perhaps not be surprising that discrete operations come into play. $\endgroup$ – Will Orrick Apr 29 '13 at 6:16
  • $\begingroup$ You could, for example, square both sides of your equation. This gets rid of $(-1)^n,$ but the quadratic becomes a quartic. The four solutions to this quartic include the two solutions to the quadratic with right hand side $-1$ and the two solutions with right hand side $1.$ The rounding question is now replaced with the question of which root to take. We obtain $n$ by taking whichever of $\log_\varphi\frac{\sqrt{5}F+\sqrt{5F^2+4}}{2}$ and $\log_\varphi\frac{\sqrt{5}F+\sqrt{5F^2-4}}{2}$ is an integer. The ambiguity for $F=1$ manifests itself in that only in this case are both integers. $\endgroup$ – Will Orrick Apr 29 '13 at 6:29

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

  • $\begingroup$ This isn't what I'm looking for. I want something exact. $\endgroup$ – Linus Apr 28 '13 at 0:45
  • $\begingroup$ What do you mean by exact? The expression above yields an integer that is the desired integer for all $n$ except $n=1,2$. You can take it $\pmod{2}$ to answer your even/odd question as well. $\endgroup$ – vadim123 Apr 28 '13 at 0:49
  • $\begingroup$ By exact, I mean that I want a general formula that doesn't fail at all. Even setting aside the failure, if you put 3 into that second expression you get 3.5764. Even taking into account that 4 should be added and not subtracted in my almost-correct initial formula, the result is 3.9075. If you add 4 the result is exactly 4. $\endgroup$ – Linus Apr 28 '13 at 1:32
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/… $\endgroup$ – lhf Apr 28 '13 at 1:58
  • 2
    $\begingroup$ @Linus: vadim123’s formula gives the exact value for all $n\ge 3$. $\endgroup$ – Brian M. Scott Apr 28 '13 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.