# How to solve for the $n$-th Fibonacci number that is greater than or equal to $N$?

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

-
When $n$ is of any significant size, then $(1-\phi)^n\approx0$, so... – Jyrki Lahtonen Sep 20 '12 at 6:43
If $N$ is an integer, so is the left-hand side, but for $n$ a positive integer we have $(1-\phi)^n$ very small and can ignore that term. – Mark Bennet Sep 20 '12 at 6:44
Thanks all, I really forgot that $(1 - \phi)^n \approx 0$. – Chan Sep 20 '12 at 6:48

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$.
@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. – Brian M. Scott Sep 20 '12 at 8:06