# Number of Fibonacci numbers in a range

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?

-
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

This question is asked in Skiena's programming challenges. Now, to find the $n^{\text{th}}$ fibonacci number, we have the following closed form expression.

$$\Large F(n) = \dfrac{1}{\sqrt{5}} \left( \left( \dfrac{1 + \sqrt{5}}{2}\right)^n - \left( \dfrac{1 - \sqrt{5}}{2} \right)^n\right)$$

Now, given $F(n)$, we can find approximately the index of the closest fibonacci number to it. Therefore, we find one $n_1$ such that $F(n_1) = a$ and another $n_2$ such that $F(n_2) = b$. Then our answer is $\mathsf{round(n_2)} - \mathsf{round(n_1)}$ where $\mathsf{round(x)}$ find the nearest integer to $x$.

-
Is the PDF in the link really freely available or is it a copyright violation? – lhf Apr 29 '14 at 12:13
I'll change the link, since I am not sure. – adijo Apr 29 '14 at 12:20

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.

-