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}$ ?
Best Answer
$\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$.