Prove the $n$th Fibonacci number is the integer closest to $\frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^n$

Question

Prove that the $n$th Fibonacci number $f_n$ is the integer that is closest to the number $$\frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^n.$$

Hi everyone, I don't really understand the problem. I have the following hint, but I don't know how to work it.

Hint: Show that the absolute value of $\frac{1}{\sqrt{5}}\left( \frac{1 - \sqrt{5}}{2} \right)^n$ is less than $1/2$.

Answer 1

The question seems to assume that you know the exact formula for $f_n$, namely $$f_n = \frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^n - \frac{1}{\sqrt{5}}\left( \frac{1 - \sqrt{5}}{2} \right)^n.$$ From here the reason the hint is useful should be clear: the expression in the hint is, up to sign, the distance between $f_n$ and the expression it's supposed to be close to.

Answer 2

We prove the hint by induction on $n$. For $n = 1$, $LHS < \dfrac{1}{\sqrt{5}} < \dfrac{1}{2}$, so the statement is true for $n = 1$. Assume it is true for $n = k$, that is: $|R_k|=\left|\dfrac{1}{\sqrt{5}}\cdot \left(\dfrac{1-\sqrt{5}}{2}\right)^k\right| < \dfrac{1}{2}$, we have:

$|R_{k+1}| = \dfrac{1}{\sqrt{5}}\cdot \left(\dfrac{\sqrt{5}-1}{2}\right)^{k+1} < |R_k| < \dfrac{1}{2}$, and the hint is proved. From this the answer follows.