0

I was reading the book "Famous Puzzles of Great Mathematicians" and in page 13 it states that:

Since the influence of the second term $((1-\sqrt{5})/2)^n/\sqrt{5}$ in the explicit formula for the nth term in fibonacci sequence $F_n=\frac{1}{\sqrt{5}}\left[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n\right]$ is negligible because $|(1-\sqrt{5})/2|<1$, it is sufficient to calculate the first term $((1+\sqrt{5})/2)^n/\sqrt{5}$ and round off the result to the nearest integer to obtain the exact(integer) value of $F_n$. To be more exact, $$F_n=\Bigg\lfloor{\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n+\frac{1}{2}\right]}\Bigg\rfloor.$$

My problem is that I can't fill the gaps for example where does $+\frac{1}{2}$ come from? I saw this related question but the thing is that already assumes the solution and reverse engineering doesn't answer me.

RobPratt
  • 45,619
Davood Karimi
  • 487
  • 2
    If you want to round $x$ to the nearest integer (rounding half-integers upwards, as usual), then $\lfloor{x + 1/2}\rfloor$ is one way to express that. Note that ignoring the small "second term" is only allowed because we know that $F_n$ is an integer. So the large "first term" must, itself, be very close to that integer. So for sufficiently large $n$, $\lfloor{x + \varepsilon}\rfloor$ will also be correct for any positive $\varepsilon$. – mjqxxxx Sep 30 '22 at 18:48
  • 1
    @mjqxxxx For Fibonacci numbers if one drops the 1/2 then the floor is wrong for odd n. One must keep the 1/2 because the straight power of the larger root is alternately just over or just under the correct value.. – coffeemath Sep 30 '22 at 19:18
  • @ coffeemath would you explain more? – Davood Karimi Sep 30 '22 at 19:26
  • 1
    The true value of $F_5$ is $5.$ When one computes $[(1+\sqrt{5})/2]^5/\sqrt{5}$ the result numericlly is $4.9959674...$ which after taking floor gives $4$ instead of the correct $5.$ The same keeps happening for larger odd numbers, but one needs a very accurate calculator which keeps more and more digits as the odd index increases. – coffeemath Sep 30 '22 at 19:33
  • 1
    Right, my point is that the value of the larger term becomes closer and closer to the true, integer value. So while $\lfloor{x + 1/2}\rfloor$ is correct (and represents the rounding operation in general), $\lfloor{x + \varepsilon}\rfloor$ is also correct for smaller values with $0 < \varepsilon < 1/2$. In particular, $\lfloor{x + 1/3}\rfloor$ is always correct. And $\lfloor{x + 1/100}\rfloor$ is correct for all $n \ge 9$. (@coffeemath is absolutely right that you cannot entirely drop the $\varepsilon$.) – mjqxxxx Sep 30 '22 at 20:01
  • @mjqxxxx Yes. smaller $\varepsilon$ work, and I think any specific positive $\varepsilon$ will work beyond some approriate index. – coffeemath Sep 30 '22 at 20:07

1 Answers1

1

$$F_n=\Bigg\lfloor{\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n+\frac{1}{2}\right]}\Bigg\rfloor$$

That looks odd... As the comment says, the second term in Binet's formula is small and can be neglected, i.e.

$$ F_n \approx \frac1{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n $$

The estimate is good enough that it actually yields the Fibonacci numbers when rounded:

$$F_n = \left\lceil\frac1{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n\right\rfloor $$ and then express rounding to nearest by the floor function:

$$\lceil x \rfloor = \lfloor x + 0.5 \rfloor$$

so that

$$F_n = \left\lfloor\frac1{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n +\frac12\right\rfloor $$

To see why this works, take the 2nd term of Binet's formula and estimate it like

$$\left|\frac1{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n\right| = \frac1{\sqrt{5}}\left|\frac{1-\sqrt{5}}{2}\right|^n \leqslant \frac1{\sqrt{5}} < 0.5$$

The un-rounded values are:

$$\begin{align} F_0 &\approx 0.44 \to 0 \\ F_1 &\approx 0.72 \to 1\\ F_2 &\approx 1.17 \to 1\\ F_3 &\approx 1.89 \to 2\\ F_4 &\approx 3.07 \to 3\\ F_5 &\approx 4.96 \to 5\\ \end{align}$$ etc.

But your formula is adding $1/(2\sqrt5)$ which is odd...

emacs drives me nuts
  • 10,390
  • 2
  • 12
  • 31