¿Por qué funciona esta prueba de Fibonacci?

Question

Para comprobar si un número $A$ es Fibonacci, todo lo que tenemos que hacer es calcular $5A^2 + 4$ y $5A^2 -4$ . Si alguno de ellos es un cuadrado perfecto, el número es Fibonacci, en caso contrario no.

¿Por qué funciona esta prueba? ¿Existe una prueba fácil?

Answer 1

Supongamos que $A = F_n$ es un número de Fibonacci. Entonces podemos demostrar fácilmente por inducción que $$ 5 F_n^2 - L_n^2 = \begin{cases} 4 \qquad &\mbox{if $n$ is odd}; \\ -4 \qquad &\mbox{if $n$ is even}. \end{cases} $$ Aquí $L_n$ denota la secuencia de Lucas, definida por $L_1=1$ , $L_2=3$ y $L_{n+2} = L_{n+1} + L_n$ . Esto significa que $5F_n^2 \pm 4$ es un cuadrado.

Por supuesto, la otra dirección es la interesante, es decir, si $5A^2 \pm 4$ es un cuadrado, entonces $A$ es un número de Fibonacci. La ecuación $5A^2\pm 4 = B^2$ reescritura a $$ \pm 1 = \left( \frac{B+A\sqrt5}{2} \right) \left( \frac{B-A\sqrt{5}}{2} \right) $$ y por lo tanto implica que (observando que $A$ y $B$ tienen la misma paridad) $\frac{B+A\sqrt5}{2}$ es una unidad en $\mathbb{Z}\left[\frac{1+\sqrt{5}}{2}\right]$ . Por el Teorema de la unidad de Dirichlet el grupo unitario de $\mathbb{Z}\left[\frac{1+\sqrt5}{2}\right]$ es de la forma $$ \mathbb{Z}\left[\frac{1+\sqrt5}{2}\right]^\ast = \{\pm 1\} \times \langle \eta \rangle = \{\pm 1\} \times \{\eta^k : k\in \mathbb{Z}\} $$ donde $\eta$ es la llamada unidad fundamental. Siempre podemos suponer que $\eta = t + u \frac{1+\sqrt5}{2}$ con $t,u \geq 0$ . Desde $u=1$ ya da una unidad $\frac{1+\sqrt5}{2}$ entonces tenemos $\eta = \frac{1+\sqrt5}{2}$ . Desde $\frac{B+A\sqrt5}{2}$ existe un número entero positivo $\ell$ tal que $$ \frac{B+A\sqrt5}{2} = \left( \frac{1+\sqrt5}{2} \right)^\ell, $$ o $ 2^{\ell-1}(B+A\sqrt5) = (1+\sqrt5)^\ell. $ Tomando los conjugados, se deduce que $ 2^{\ell-1}(B-A\sqrt5) = (1-\sqrt5)^\ell. $ Ahora vemos que $$ A = \frac{2^{\ell-1}(B+A\sqrt5) - 2^{\ell-1}(B-A\sqrt5)}{2^{\ell} \sqrt 5} = \frac{(1+\sqrt5)^\ell - (1-\sqrt5)^\ell}{2^{\ell} \sqrt 5} = \frac{1}{\sqrt{5}}\left( \left( \frac{1+\sqrt5}{2} \right)^\ell - \left( \frac{1-\sqrt5}{2} \right)^\ell\right) = F_\ell $$ donde utilizamos el Fórmula de Euler-Binet para el último paso.