1
$\begingroup$

The general formula for the $n$-th Fibonacci number is:

$\frac{\phi^n - (1 - \phi)^n}{\sqrt{5}}$

where

$\phi = \frac{1 + \sqrt{5}}{2}$

Given $N$, is there a way to solve for $n$ in this inequality $\frac{\phi^n - (1 - \phi)^n}{\sqrt{5}} \ge N\text{ ?}$

  • 0
    Thanks all, I really forgot that $(1 - \phi)^n \approx 0$.2012-09-20

1 Answers 1

5

In fact the second term in the numerator is so small that for all $n\ge 0$, $F_n$ is the integer nearest $\varphi^n/\sqrt5$. Equivalently, $F_n=\left\lfloor\frac{\varphi^n}{\sqrt5}+\frac12\right\rfloor\;.$ When $n$ is odd, $\varphi^n/\sqrt5$ is a little more than $F_n$, and when $n$ is even, $\varphi^n/\sqrt5$ is a little less than $F_n$, but to a first approximation you want $\varphi^n\ge N\sqrt5$, or $n\ge\frac{\ln N+\frac12\ln 5}{\ln\varphi}\;.\tag{1}$ For $N=13$ the righthand side of $(1)$ is about $7.002463651556$, and indeed $F_7=13$; for $N=21$ the righthand side of $(1)$ is about $7.999058197424$, and $F_8$ is $13$. Even taking $N=2$ isn’t too bad: the righthand side of $(1)$ is about $3.112696028597$, and of course $F_3=2$.

On this evidence, even without doing a closer analysis of the error, it’s clear that $\left\lceil\frac{\ln N+\frac12\ln 5}{\ln\varphi}\right\rceil$ is going to be right except when $N=F_n$ for an odd $n$, when the fractional part of the righthand side of $(1)$ is very, very small even for rather modest values of $N$.

  • 0
    @Chan: You’d need to be able to tell when the fractional part of that fraction was too small for $N$ to be anything but $F_{2k+1}$. In other words, you need to know how small it can be when $N=F_{2k+1}+1$ for some $k$. I suspect that a less superficial analysis would make this possible, but I’ve not actually tried.2012-09-20