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.
Best Answer
Well, $-1<\phi<1$, so $-1<\phi^n\leq1$ for all $n\geq0$, and $\sqrt5>\sqrt4=2$.