A proof regarding the Fibonacci Sequence.

Question

Say, $F_i$ describes the $i\:th$ term of the Fibonacci sequence where $i\geq0$.

I am trying to prove $F_i=\lfloor\dfrac{\phi^i}{\sqrt{5}}+\dfrac{1}{2}\rfloor$, where $\phi$ and $\hat\phi$ are the roots of the equation $x^2-x-1=0$.

Also, $F_i=\dfrac{\phi^i-\hat\phi^{i}}{\sqrt5}$ where {$\phi=\dfrac{1+\sqrt5}{2},\hat\phi=\dfrac{1-\sqrt5}{2}$}.

Now, the text I am reading, does it like as below:

We know $|\hat\phi|<1$ => $|\hat\phi^{i}|<1$ => $\dfrac{|\hat\phi^{i}|}{\sqrt5}<\dfrac{1}{\sqrt5}<\dfrac{1}{2}$

Using the inequality above, we have $|F_i|<\dfrac{|\phi^{i}|}{\sqrt5}+\dfrac{1}{2}$, since $\phi >0$ and $F_i\geq0$, we have $F_i<\dfrac{\phi^{i}}{\sqrt5}+\dfrac{1}{2}$

Now after this, the text says directly - 'Hence, $F_i=\lfloor\dfrac{\phi^i}{\sqrt{5}}+\dfrac{1}{2}\rfloor$ '.

I don't quite understand that how from the final inequality, we came to the final conclusion. Can anyone help ?

Answer 1

If I'm right ( others will correct me if i'm not )

$$\left|\frac{\overline{\phi}^{i}}{\sqrt{5}}\right| < \frac{1}{2}$$ Hence $$ -\frac{1}{2} <\frac{\overline{\phi}^{i}}{\sqrt{5}} < \frac{1}{2} $$ So $$ \frac{\phi^{i}}{\sqrt{5}}-\frac{1}{2} < F_i < \frac{\phi^{i}}{\sqrt{5}}+\frac{1}{2} $$

Then $F_i$ is an integer which it is in $\displaystyle \left]a-\frac{1}{2},a+\frac{1}{2}\right[$ hence in $\displaystyle \left]\lfloor a-\frac{1}{2}\rfloor,\lfloor a+\frac{1}{2}\rfloor\right]$ We can conclude that

$$ F_i=\lfloor\frac{\phi^{i}}{\sqrt{5}}+\frac{1}{2}\rfloor $$

Answer 2

Since $\phi+\hat\phi=1$, we have $$ F_n=\frac{\phi^n-(1-\phi)^n}{\sqrt5} $$ Since $-\frac12\lt\frac{(1-\phi)^n}{\sqrt5}\lt\frac12$, $$ F_n-\frac12\lt\frac{\phi^n}{\sqrt5}\lt F_n+\frac12 $$ Thus, $$ F_n\lt\frac{\phi^n}{\sqrt5}+\frac12\lt F_n+1 $$ Therefore, $$ F_n=\left\lfloor\frac{\phi^n}{\sqrt5}+\frac12\right\rfloor $$