# Fibonacci rounding formula proof

Recently I had to solve a little problem related with Fibonacci numbers. I was using the Binet's formula for that:

$$F_{n} = \frac{\Phi^n - \phi^n}{\sqrt{5}}$$

The effective solution I got by using computation by rounding formulas, related to Binet's formula that arises from simple inequality:

$$\left| \frac{\phi^n}{\sqrt{5}} \right| < \frac{1}{2}, \quad n \leq 0.$$

$$F_{n} =\left\lfloor \frac{\Phi^n}{\sqrt{5}} + \frac{1}{2} \right\rfloor$$

I understand how it can be derived from above mentioned inequality, but I don't get it how I can derive that inequality rigorously in the first place. Any explanations would help me a lot! Thank you in advance.

Well, $$-1<\phi<1$$, so $$-1<\phi^n\leq1$$ for all $$n\geq0$$, and $$\sqrt5>\sqrt4=2$$.

• Thank you! Now I get it! – Eric Rovell Mar 5 at 11:32
• $-2<1$, but $(-2)^2=4>1$. – egreg Mar 5 at 11:57

Note that $$\phi=\frac{1-\sqrt{5}}{2}$$, so $$|\phi|=\frac{\sqrt{5}-1}{2}<1.$$ Also, $$\sqrt{5}>2$$.

• Thank you, it helped me! – Eric Rovell Mar 5 at 11:32