1
$\begingroup$

I'm reading a book about algorithms and there is some explanation of Fibonacci numbers. So it says that

$$ F_i = \frac{\phi^i - \hat{\phi^i}}{\sqrt{5}}, $$ where $\phi^i$ is golden ratio and $\hat{\phi^i}$ is its conjugate.

I understand that if $|\hat{\phi^i}| < 1$ then $\frac{|\hat{\phi^i}|}{\sqrt{5}} < \frac{1}{2}$. Then the author says that the previous inequality implies that $$ \left\lfloor{\frac{\phi^i}{\sqrt{5}} + \frac{1}{2}} \right\rfloor. $$ So, my first quesiton is why the author is using '$+$' while in the first expression we have '$-$' ?

And the second question is related to the following author's conclusion about the last expression:

which is to say that the ith Fibonacci number $F_i$ is equal to $\frac{\phi^i}{\sqrt{5}}$ rounded to the nearest integer.

Could someone please explain to me why the author ignores $\frac{1}{2}$ ?

$\endgroup$
2
$\begingroup$

$\lfloor x+1/2\rfloor$ is rounding to the nearest integer. $\lfloor x\rfloor$ truncates the decimal expansion of $x$, so in order to get the nearest integer instead of always getting the one below it, you have to add $1/2$.

$\endgroup$
  • $\begingroup$ Oh, I got it. The nearest integer is not the same as a result of the floor function. Thank you very much for good explanation. By the way, have you had a chance to look at my first question? I still don't understand why the author change the sign in the formula. Why he is adding $\frac{1}{2}$ while in the formula we have $\frac{\phi^i - \hat{\phi^i}}{\sqrt{5}}$ ? Just to get the nearest integer? If so, it's a bit strange for me.. $\endgroup$ – E. Shcherbo Jul 25 at 16:08
  • $\begingroup$ Think of the "rounding function" $r(x) = \lfloor x+1/2\rfloor$. The author is saying $F_i = r(\phi^i/\sqrt{5})$. The $1/2$ has nothing to do with the explicit formula--it's just part of the rounding operation. $\endgroup$ – eyeballfrog Jul 25 at 16:10
  • $\begingroup$ Ok, then what I'm worrying about is why is he ignoring the second part of the first expression and to get a Fibonacci number using only the first part of it? And why is he saying that this one $\frac{|\hat{\phi^i}|}{\sqrt{5}} < \frac{1}{2}$ implies this one $ \left\lfloor{\frac{\phi^i}{\sqrt{5}} + \frac{1}{2}} \right\rfloor. $? I'm sorry for my stupidity, just want to completely understand it. $\endgroup$ – E. Shcherbo Jul 25 at 16:25
  • $\begingroup$ $|\hat{\phi}|<1$, so as you raise it to higher powers, it gets closer and closer to zero. Thus, rounding to the nearest integer on $\phi^i/\sqrt{5}$ always gets the right answer, because the correction term $\hat{\phi}^i/\sqrt{5}$ is always small. $\endgroup$ – eyeballfrog Jul 25 at 17:02
  • $\begingroup$ Ok, I see. Thought something like this. Thank you very much for your help! $\endgroup$ – E. Shcherbo Jul 25 at 17:12

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.