¿Pregunta no trivial sobre los números de Fibonacci?

Question

Estoy buscando una pregunta no trivial, pero no superdifícil, relativa a los números de Fibonacci. Debe ser de un nivel adecuado para un curso de grado.

Aquí hay un ejemplo (no tan bueno) del tipo de cosas que estoy buscando.

a) Demuestre que todo número entero positivo puede representarse en binario sobre la base de los números de Fibonacci. Es decir, demuestre que para todo $n$ existen bits $x_1,\ldots,x_k$ tal que $n = \sum_{i=1}^kx_iF_i$ .

b) Dé un algoritmo para incrementar dichos números en tiempo amortizado constante.

¿Alguna idea para mejorarlas?

Answer 1

Estrechamente relacionado con la respuesta de Zev es que si $p$ es un primo no igual a $2$ o $5$ entonces $F_p \equiv \left( \frac{p}{5} \right) \bmod p$ . Los números de Fibonacci también tienen una relación especial con las fracciones continuas relacionadas con la segunda parte de la respuesta de Nurdin, sobre la que escribí una antigua entrada en el blog ici . Hay mucho que decir sobre ellos, ¡así que me gustaría que fueras un poco más específico!

Editar: Por ejemplo, uno de mis ejercicios favoritos de Fibonacci (que está en algún lugar de Stanley) es escribir la función generadora de $\sum_{n \ge 0} F_{n+1}^2 x^n$ sin ningún tipo de cálculo, utilizando el hecho de que $F_{n+1}$ es el número de formas de embaldosar un tablero de longitud $n$ con baldosas de longitud $1$ y $2$ , interpretando $F_{n+1}^2$ como el número de pares de tales tilings, y determinando los tilings "primos" que pueden ocurrir (la palabra clave elegante aquí es "factorización monoide").

Edición #2: Mientras estoy en una inclinación combinatoria, hay otro relación entre los números de Fibonacci y las fracciones continuas, pero esta vez de series de potencias. La función generadora de los números catalanes se puede describir como una fracción continua que corresponde a una definición recursiva de árboles enraizados ordenados, y uno de los "convergentes" de esta serie de potencias es la función generadora de los números pares de Fibonacci, lo que "explica" por qué los números pares de Fibonacci se aproximan a los números catalanes. También escribí una entrada en el blog sobre esto ici . Hay muchas cosas interesantes aquí, aunque no estoy seguro de cómo convertirlas en un buen problema.

Answer 2

Para los estudiantes de grado que conozcan algo de teoría de la probabilidad, hay dos documentos interesantes http://front.math.ucdavis.edu/1008.3202 y http://front.math.ucdavis.edu/1008.3204 . Estos trabajos se refieren a las propiedades estadísticas del número de sumandos cuando se escribe un número entero como una suma de números de Fibonacci no consecutivos, y a las generalizaciones a otras secuencias de números. Todos los autores de estos trabajos, excepto uno, eran estudiantes universitarios cuando los escribieron.

Answer 3

La Olimpiada Internacional de Matemáticas de 1981 incluyó lo siguiente como problema final de la primera jornada:

Determinar el valor máximo de $m^2+n^2$ , donde $m$ y $n$ son números enteros que satisfacen $m,n \in \lbrace 1,2,\ldots,1981\rbrace$ y $(n^2-mn-m^2)^2 = 1$ .

[1981 fue una de las dos OMI en las que participé. Primero lo resolví utilizando la maquinaria estándar de las ecuaciones de Pell, pero reconocí la solución máxima $(987,1597)$ y luego escribió una solución en la línea prevista].

Answer 4

Aquí está mi favorito: las identidades de la familia Zeckendorf (por Philip Matchett Wood y Doron Zeilberger).

Todo lo suficientemente alto (= lo suficientemente alto para que los lados de la derecha tengan sentido) entero $n$ satisface

$1f_n=f_n$ ;

$2f_n=f_{n-2}+f_{n+1}$ ;

$3f_n=f_{n-2}+f_{n+2}$ ;

$4f_n=f_{n-2}+f_n+f_{n+2}$ ;

$5f_n=f_{n-4}+f_{n-1}+f_{n+3}$ ;

etc.

El patrón detrás de estas identidades es: $kf_n$ a la izquierda, una suma de $f_{n+\alpha}$ a la derecha, donde no hay $\alpha$ ocurre dos veces, y no hay dos enteros consecutivos que ocurran ambos como $\alpha$ 's.

Resulta que dicha identidad es única para todos los $k$ .

(Plugin desvergonzado:) Se generaliza.

Answer 5

1) Para todo n natural existe un k>0 natural tal, que $n|F_k$

2) Considere todos los pares de números naturales $x,y\le n$ . Entonces, el peor caso para el algoritmo de Euclides para GCD es un par $(F_{k-1}, F_k)$ , donde $F_k$ - el mayor número de Fibonucci, que no excede de n.

Actualización: Hay un libro Números de Fibonacci de Vorobyev, puede ser útil. Matiyasevich utilizó algunos datos sobre los números de Fibonacci de este libro en su solución del décimo problema de Hilbert.