Showing that $f_n$ is the number closest to $\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n$

Question

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.

Answer 1

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