# Fibonacci and golden ratio

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}$$ ?

• Is this "book" you speak of, by any chance Introduction to Algorithms, by Cormen et.al? Aug 26 '20 at 14:08
• Yes, this is Introduction to Algorithms Aug 26 '20 at 14:48

$$\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$$.
• 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.. Jul 25 '19 at 16:08
• 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. Jul 25 '19 at 16:10
• 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. Jul 25 '19 at 16:25
• $|\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. Jul 25 '19 at 17:02