Probability that a chosen number will be a Fibonacci number

Question

Suppose that I randomly choose an integer $x$ with $1 \leq x \leq n$ where $n$ is a natural number.

What is the probability that $x$ will be a Fibonacci number?

Answer 1

Given some $n$, you can find the corresponding number of distinct Fibonacci numbers not greater than $n$ by: $$\lfloor {\log_\varphi}[\sqrt5(n+\frac{1}{2})] \rfloor -1$$ Where $\varphi=\frac{1+\sqrt5}{2}$ is the (amazing) golden ratio.

Thus, the probability of some $N\le n$ chosen at random, to land on a Fibonacci number is: $$P(n)=\frac{\lfloor {\log_\varphi}[\sqrt5(n+\frac{1}{2})] \rfloor -1}{n}$$

This is the totally exact probability, if it matters. :)

Here are some graphs showing $n\mapsto P(n)$ (1 to 50 and 50 to 500):

Answer 2

Well, an approximate behaviour for large Fibonnaci number is $a_n\sim \phi^n$ where $\phi=(\sqrt{5}+1)/2$.

So when $n\to\infty$, the approximate number of Fibonacci number in $[1,n]$ will be $\lfloor\log_\phi^n\rfloor$.

So the probability you are looking for is approximately $$ p_n=\lfloor\log_\phi^n\rfloor/n $$

P.S. The reason for above is that Fibonnaci series can be shown as $$ a_n=\left(\frac{\sqrt{5}+1}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n $$

Answer 3

By the formula of Moivre-Binet, the $n$-th Fibonacci-number is given by $$F_n = \frac{1}{\sqrt{5}}\left ( \left (\frac{1+\sqrt{5}}{2} \right)^n-\left( \frac{1-\sqrt{5}}{2} \right)^n \right).$$ As $\left |\frac{1}{\sqrt{5}}\left( \frac{1-\sqrt{5}}{2} \right)^n \right | <\frac{1}{2}$ for all $n$, this can be written as $$F_n = \Big [\frac{1}{\sqrt{5}}\phi^n \Big ]$$ where $\phi$ is the golden ratio and the brackets indicate rounding to the nearest integer. This gives us a formula for $G(x)$, the number of Fibonacci-numbers below $x$: $$G(x) = \left \lfloor \frac{\log(\sqrt{5}x)}{\log(\phi)}\right \rfloor - \begin{cases} 0 & \text{if $F_{2n-1} = x$ for some $n \in \Bbb N$} \\ 1 & \text{else} \end{cases}$$ As the probability $\Bbb P(n) = \Bbb P(1\leq x\leq n \text{ is Fibonnaci number })$ is $G(n)/n$, we get an exact formula for the probability, and the asymptotic result $$P(n) \sim \frac{\log(n)}{n\log(\phi)}. $$