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