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 definition of the Fibonacci numbers is given by:

$$\begin{align}f_1 &= 1;\\ f_2 &= 2;\\ f_n &= f_{n-1} + f_{n-2},\qquad (n >= 3); \end{align}$$

now we are given two numbers $a$ and $b$, and we have to calculate how many Fibonacci numbers are in the range $[a,b]$. How can we calculate it?

share|improve this question
    
Naively just compute all Fibonacci numbers smaller or equal to $b$ and count. Maybe you should clarify what you mean by 'calculate'. A closed form dependent on $a$ and $b$ will probably not exist. –  Simon Markett Oct 23 '13 at 10:22
    
Your definition of Fibonacci numbers is off by one from the standard indexing. Normally $f_2=1, f_3=2$. My answer uses the standard indexing. The final answer doesn't change as we are subtracting two indices. –  Ross Millikan Oct 23 '13 at 10:43
    
'calculate'means total fibonacci numbers between the range... –  rock321987 Oct 23 '13 at 11:05
    
@RossMillikan...got it –  rock321987 Oct 23 '13 at 11:06
add comment

1 Answer

up vote 5 down vote accepted

We know that $F_n\approx \frac {\phi^n}{\sqrt 5}$, so given $a$, the next larger Fibonacci number is $F_k$, where $k= \left \lceil\frac {\log (a\sqrt 5)}{\log \phi }\right \rceil$. Similarly the $F_m$ below $b$ is $m= \left \lfloor\frac {\log (b\sqrt 5)}{\log \phi }\right \rfloor$, then there are $m-k+1$ between $a$ and $b$. You have to think about what you want if $a$ or $b$ are themselves Fibonacci numbers.

share|improve this answer
add comment

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.