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

  • 1
    When $n$ is of any significant size, then $(1-\phi)^n\approx0$, so...2012-09-20
  • 0
    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.2012-09-20
  • 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
    Nice write-up and explanation. Thanks a lot Brian!2012-09-20
  • 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