¿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

Mis identidades favoritas son las fórmulas $$ F_{n+1}=\sum_{2k\le{n}}{n-k\choose k}\ =\sum_{i\in\mathbb{Z}}(-1)^i {n\choose{\lfloor {(n+5i)}/2\rfloor}}$$ y $$ F_{n}=\sum_{2k\le{n-1}}{n-1-k\choose k}\ =\sum_{i\in\mathbb{Z}}(-1)^i {n\choose{\lfloor {(n+5i-1)}/2\rfloor}}$$ . Han sido encontrados por I. Schur en 1917. De hecho, ha demostrado un análogo de q que implica inmediatamente las identidades de Rogers-Ramanujan.

Answer 2

Los recíprocos de los números de Fibonacci $F_2 = 1$ , $F_4 = 3$ , $F_8 = 21$ , $F_{16} = 987$ , $F_{32} = 2178309$ , . . . de orden de potencia de dos se pueden sumar en forma cerrada: $$ \sum_{n=1}^\infty \frac1{F_{2^n}} = \frac{5 - \sqrt{5}}{2} \, . $$ De manera más general, $$ \sum_{n=1}^\infty \frac1{F_{2^n k}} = \frac{\sqrt{5}}{\varphi^{2k}-1} $$ ( $k=1,2,3,\ldots$ ); comparando las sumas para $k$ y $2k$ se obtiene la prueba por suma telescópica.

(Este es un caso especial de una fórmula que apareció recientemente en una pregunta de Math Stackexchange pregunta , que se refiere a una pregunta anterior nin que Jeffrey Shallit escribió que el $k=1$ la fórmula es "conocida", pero sin más referencias [su respuesta cita el artículo de Salzer en el 1947 Mensualmente que, sin embargo, no contiene esto $(5-\sqrt5)/2$ fórmula]; parece el tipo de resultado que es mucho más fácil de derivar que de localizar en la literatura).

Answer 3

Una pequeña mejora a su pregunta sería insistir en que si $x_i=1$ entonces $x_{i+1}=0$ y pedir la singularidad. Además, puedes generar un montón de buenas preguntas observando que las potencias de la matriz 2 por 2 con la primera fila 11 y la segunda fila 10 te dan matrices con la primera fila $F_{n+1}, F_n$ y la segunda fila $F_n,F_{n-1}$ . Se les puede pedir que lo demuestren por inducción y que luego deduzcan consecuencias como $F_n^2-F_{n+1}F_{n-1}=\pm 1$ . O puedes preguntar sólo por las consecuencias y ver qué pruebas se les ocurren (los argumentos inductivos son posibles). No estoy seguro del nivel de dificultad que buscas, pero son hechos agradables.

Answer 4

Si no le gusta su propio ejemplo, puede que no le guste éste pero algunos de sus alumnos podrían encontrarlo interesante. Lo descubrí junto con Roger House cuando era estudiante.

Dejemos que $F_1$ sea la matriz 1x1 $1$ y crear por aumento las matrices 0-1 de mayor dimensión de la siguiente manera: (¡Me encantan las etiquetas < PRE >!)

         1 1 0 0 ... 0
         0
         1
F\_(n+1)= 0    F\_n                         1 1 0 0
         0                                0 1 1 0
         :                   1 1          1 0 1 1
         0             , so  0 1 is F\_2,  0 1 0 1 is F\_4, and so on. 

Entonces $\det(F_n) = fib(n)$ Lo que es fácil. Lo que es un poco más difícil es que puedes alternar los bits de $F_n$ para obtener una matriz 0-1 con determinante $k$ para cualquier prescripción $k$ con $0 \le k \le fib(n)$ .

A Miodrag Zivkovic le gustó lo suficiente un ejemplo similar como para incluirlo en su artículo en http://arXiv.org/abs/math.CO/0511636 . Puede consultar su documento para ver si ese ejemplo es el tipo de cosa para sus estudiantes.

Gerhard "Ask Me About System Design" Paseman, 2010.01.15

Answer 5

Dos respuestas:

1. El texto casi enciclopédico de Thomas Koshy Números de Fibonacci y Lucas con aplicaciones contiene muchísimos resultados sobre los números de Fibonacci, muchos de los cuales pueden demostrarse utilizando técnicas al alcance de los estudiantes universitarios.

2. Como una variante de la respuesta de gowers sobre la toma de potencias de la matriz

   1 1
   1 0

Escribí un papel hace unos años sobre el uso de la propiedad de la suma de determinantes y esta matriz para demostrar algunas identidades de Fibonacci. Apareció en La Revista de Matemáticas de la Universidad y es muy de nivel universitario.