<s>[INST] Showing that $f_n$ is the number closest to $\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n$ I want to prove that the the $n$th Fibonacci number $f_n$ is the integer closest to $\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n$. What would be a rigorous way to go about this? I assume I'll have to use a recurrence relation and maybe Binet's Forumla. I just don't know how to go about tying it all together, so any advice on how to proceed would be much appreciated.
 [/INST] Copy-paste from Wikipedia:
Like every sequence defined by a linear recurrence with constant coefficients, the Fibonacci numbers have a closed-form solution. It has become known as Binet's formula, even though it was already known by Abraham de Moivre:
$$F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5}$$
where
$$\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\cdots\,$$
is the golden ratio, and
$$\psi = \frac{1 - \sqrt{5}}{2} = 1 - \varphi = - {1 \over \varphi} \approx -0.61803\,39887\cdots$$
Since $\psi = -\frac{1}{\varphi}$, this formula can also be written as
$$F_n = \frac{\varphi^n-(-\varphi)^{-n}}{\sqrt 5}$$
To see this, note that $\phi$ and $\psi$ are both solutions of the equations
$$x^2 = x + 1,\, x^n = x^{n-1} + x^{n-2},\,$$
so the powers of φ and ψ satisfy the Fibonacci recursion. In other words
$$\varphi^n  = \varphi^{n-1} + \varphi^{n-2}\, $$
and
$$\psi^n = \psi^{n-1} + \psi^{n-2}\, .$$
It follows that for any values $a$ and $b$, the sequence defined by
$$U_n=a \varphi^n + b \psi^n\,$$
satisfies the same recurrence
$$U_n=a \varphi^{n-1} + b \psi^{n-1} + a \varphi^{n-2} + b \psi^{n-2} = U_{n-1} + U_{n-2}.\,$$
If $a$ and $b$ are chosen so that $U_0=0$ and $U_1=1$ then the resulting sequence $U_n$ must be the Fibonacci sequence. This is the same as requiring $a$ and $b$ satisfy the system of equations:
$$\left\{\begin{array}{l} a + b = 0\\ \varphi a + \psi b = 1\end{array}\right.$$
which has solution
$$a = \frac{1}{\varphi-\psi} = \frac{1}{\sqrt 5},\, b = -a$$
producing the required formula.
Computation by rounding
Since
$$\frac{|\psi|^n}{\sqrt 5} < \frac{1}{2}$$
for all $n \geq 0$, the number $F_n$ is the closest integer to
$$\frac{\varphi^n}{\sqrt 5}\, .$$
Therefore it can be found by rounding, or in terms of the floor function:
$$F_n=\bigg\lfloor\frac{\varphi^n}{\sqrt 5} + \frac{1}{2}\bigg\rfloor,\ n \geq 0.$$
Or the nearest integer function:
$$F_n=\bigg[\frac{\varphi^n}{\sqrt 5}\bigg],\ n \geq 0.$$
Similarly, if we already know that the number $F > 1$ is a Fibonacci number, we can determine its index within the sequence by
$$n(F) = \bigg\lfloor \log_\varphi \left(F\cdot\sqrt{5} + \frac{1}{2}\right) \bigg\rfloor$$
</s>