Probabilidad de que un número elegido sea un número de Fibonacci

Question

Supongamos que elijo al azar un número entero $x$ con $1 \leq x \leq n$ donde $n$ es un número natural.

¿Cuál es la probabilidad de que $x$ será un número de Fibonacci?

Answer 1

Teniendo en cuenta algunos $n$ se puede encontrar el número correspondiente de números de Fibonacci distintos no mayores que $n$ por: $$\lfloor {\log_\varphi}[\sqrt5(n+\frac{1}{2})] \rfloor -1$$ Donde $\varphi=\frac{1+\sqrt5}{2}$ es el (increíble) proporción áurea .

Por lo tanto, la probabilidad de algún $N\le n$ elegido al azar, para caer en un número de Fibonacci es: $$P(n)=\frac{\lfloor {\log_\varphi}[\sqrt5(n+\frac{1}{2})] \rfloor -1}{n}$$

Esta es la probabilidad totalmente exacta, si es que importa. :)

Estos son algunos gráficos que muestran $n\mapsto P(n)$ (1 a 50 y 50 a 500):

Answer 2

Pues bien, un comportamiento aproximado para un número grande de Fibonnaci es $a_n\sim \phi^n$ donde $\phi=(\sqrt{5}+1)/2$ .

Así que cuando $n\to\infty$ el número aproximado de Fibonacci en $[1,n]$ será $\lfloor\log_\phi^n\rfloor$ .

Así que la probabilidad que buscas es aproximadamente $$ p_n=\lfloor\log_\phi^n\rfloor/n $$

P.D. La razón de lo anterior es que la serie de Fibonnaci puede mostrarse como $$ a_n=\left(\frac{\sqrt{5}+1}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n $$

Answer 3

Según la fórmula de Moivre-Binet, el $n$ -El número de Fibonacci número 1 viene dado por $$F_n = \frac{1}{\sqrt{5}}\left ( \left (\frac{1+\sqrt{5}}{2} \right)^n-\left( \frac{1-\sqrt{5}}{2} \right)^n \right).$$ Como $\left |\frac{1}{\sqrt{5}}\left( \frac{1-\sqrt{5}}{2} \right)^n \right | <\frac{1}{2}$ para todos $n$ se puede escribir como $$F_n = \Big [\frac{1}{\sqrt{5}}\phi^n \Big ]$$ donde $\phi$ es la proporción áurea y los paréntesis indican el redondeo al entero más cercano. Esto nos da una fórmula para $G(x)$ el número de números de Fibonacci por debajo de $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}$$ Como la probabilidad $\Bbb P(n) = \Bbb P(1\leq x\leq n \text{ is Fibonnaci number })$ es $G(n)/n$ obtenemos una fórmula exacta para la probabilidad, y el resultado asintótico $$P(n) \sim \frac{\log(n)}{n\log(\phi)}. $$