floor equation for fibonacci sequence

208 Views Asked by At

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.

1

There are 1 best solutions below

2
On

$$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...