3
$\begingroup$

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}$?

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

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.

$\endgroup$
  • $\begingroup$ 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??? $\endgroup$ – user3019105 Nov 15 '14 at 17:35
  • 1
    $\begingroup$ @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. $\endgroup$ – user14972 Nov 16 '14 at 0:14
  • $\begingroup$ 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? $\endgroup$ – user3019105 Nov 16 '14 at 8:59
2
$\begingroup$

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.

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

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.