Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
    
Nice write-up and explanation. Thanks a lot Brian! –  Chan Sep 20 '12 at 7:28
    
@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
    
Thanks again Brian. –  Chan Sep 20 '12 at 8:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.