0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.