For a large number x>0, how many Fibonacci numbers are there in the interval [1,x]? I have saw the corresponding results in certain places but I have forgotten now. Can anyone help me? Thanks!
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ If you know that $F_n=a\omega^n+b\omega^{-n}$ with $a,b$ constant and $\omega=(1+\sqrt5)/2$, you can conclude. $\endgroup$– Denis SerreOct 11, 2010 at 9:14
-
1$\begingroup$ Very closely related problem - mathoverflow.net/questions/39124/fibonacci-sequence-inversion $\endgroup$– Nurdin TakenovOct 11, 2010 at 10:02
-
1$\begingroup$ I think this question should be closed, because the first hit on Google for "Fibonacci number" gives you the answer: en.wikipedia.org/wiki/… $\endgroup$– S. Carnahan ♦Oct 11, 2010 at 11:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Let $G:=(1+\sqrt{5})/2;g:=(1-\sqrt{5})/2$, then the $n$-th Fibonacci number is $\frac{1}{\sqrt{5}}(G^n-g^n)$. Note that $|g|<1$. Hence the number of Fibonacci numbers $\le x$ is $\frac{\log \sqrt{5}x}{\log G}$ plus or minus 1 (and it is easy to see when you need to add or subtract 1).
-
$\begingroup$ @Mark - Don't you mean
$\frac{\log \sqrt{5} x}{\log G}$
? $\endgroup$ Oct 11, 2010 at 9:59 -
$\begingroup$ @Moshe: Yes, of course. When I first typed the answer, I denoted $G$ by $g$ and $g$ by $G$, but then I decided that $g$ cannot be bigger than $G$, so I switched the notation, but not everywhere. $\endgroup$– user6976Oct 11, 2010 at 10:21