¿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

Aquí tienes algunas de las más chulas que he escuchado:

1) Dejemos que $a$ sea un número entero positivo. Entonces $a$ es un número de Fibonacci si y sólo si al menos un miembro del conjunto { $5a^{2}-4, 5a^{2}+4$ } es un cuadrado perfecto.

Creo que el resultado es original con el profesor Ira Gessel.

2) Dejemos que $\phi$ denotan la función totiente de Euler. Demostrar que $\phi(F_{n}) \equiv 0 \pmod{4}$ si $n \geq 5$ .

La prueba consiste en una aplicación inesperada del teorema de Lagrange en la teoría de grupos. Supongo que hay otras formas de demostrarlo, pero este enfoque siempre será de mi agrado. El problema fue planteado y resuelto en el Monthly en los años 70 (si mi memoria no me falla). Busca todas las entradas de Clark Kimberling en esa revista y seguro que lo encuentras.

3) ¿Puedes encontrar $(a,b,c) \in \mathbb{N}^{3}$ tal que $ 2 < a < b < c$ y $F_{a} \cdot F_{b} = F_{c}$ ?

Este problema sería trivial si en lugar del $\cdot$ que habíamos colocado un signo más allí. En cualquier caso, no hay que asustarse con esta propuesta. Lo único que hay que recordar es el correspondiente teorema del divisor primitivo .

4) Ben Linowitz mencionó anteriormente un hermoso resultado del profesor Florian Luca, a saber:

No hay números perfectos en la secuencia de Fibonacci.

Leí el documento en mi primer año y no me pareció tan difícil de seguir. La parte fácil de esta bonita nota reside en la demostración del hecho de que no hay números perfectos pares en la secuencia de Fibonacci. Supongo que este resultado es lo suficientemente interesante como para merecer ser considerado en esas conferencias que pretende dar. Si este propuesta no es exactamente su idea de emoción, puede echar un vistazo a algunos de los otros trabajos del profesor Florian. Él escribe un montón sobre las secuencias de recurrencia. Otro teorema suyo, estrechamente relacionado con el tema de esta discusión, establece que

No existe ningún grupo simple finito no abeliano cuyo orden sea un número de Fibonacci.

5) Por último, pero no menos importante... Demostrar que la secuencia { $F_{n+1}/F_{n}$ } $_{n \in \mathbb{N}}$ converge y utilizamos este hecho para derivar el desarrollo de la fracción continua para la proporción áurea.

Este debe ser conocido, pero sería bueno ver lo que sus estudiantes vienen con...

Añadido (20/11/2010) Acabo de darme cuenta de que el Asociación Fibonacci. ha puesto a disposición los artículos publicados en La revista Fibonacci Quarterly entre 1963 y 2003. Estoy seguro de que encontrará mucho material adicional entre esos archivos que tan generosamente han liberado para nuestro disfrute. Por ejemplo, se puede encontrar el artículo seminal de J. H. E. Cohn que K. Buzzard menciona a continuación ici .

Answer 2

Un aspecto accesible (e interesante) de los números de Fibonacci es su periodicidad en función de varios números enteros, especialmente los primos y las potencias primarias. Un ejemplo de resultado accesible es que si $k(p)$ es el período de los números de Fibonacci módulo a un primo $p$ entonces $k(p)\mid p^2-1$ . Se pueden obtener resultados más nítidos examinando si 5 es un residuo cuadrático mod $p$ (piense en la importancia de $\frac{1\pm\sqrt{5}}{2}$ a los números de Fibonacci). Se pueden demostrar cosas sobre esta periodicidad directamente, o reducir la matriz 2x2 que menciona Gowers modulo $p$ y obtener lo mismo, dependiendo de lo que quiera enfatizar a sus alumnos. Algunos buenos recursos para este tema son

http://en.wikipedia.org/wiki/Pisano_period

http://euclid.math.temple.edu/~renault/fibonacci/fib.html

Otra cosa interesante sobre los números de Fibonacci es su aparición como sumas de "diagonales" en el Triángulo de Pascal, como en esta imagen:

Sin embargo, este hecho es demostrable simplemente por inducción, así que tal vez esto sea demasiado fácil para lo que tienes en mente.

Answer 3

En 1964, J. H. E. Cohn demostró que el mayor cuadrado de la secuencia de Fibonacci era 144. La prueba utiliza datos estándar sobre los cuadrados mod $p$ hasta la reciprocidad cuadrática, de forma ingeniosa. Es MR0163867 en Math Reviews si quieres buscar esto. Esta es una de esas pruebas que se pueden leer y entender fácilmente, pero que sería un demonio descubrir por uno mismo. He dado este problema a estudiantes universitarios como un ejercicio superlargo con pistas.

Answer 4

La relación utilizada por Matiyasevich (Matijasevich, Матиясевич), a la que aludió N. Takenov más arriba/abajo, es la siguiente:

Si $F_{n}^{2}|F_{m}$ entonces $F_{n}|m$ ...... (20)

En el número de otoño de 1992 de la revista Intelligencer había una nota de Matiyasevich donde explicaba, entre otras cosas, la importancia de esa relación en su trabajo sobre el décimo problema de Hilbert. Aquí tienes un extracto de esa nota:

"No es difícil demostrar esta notable propiedad de los números de Fibonacci después de se ha dicho, pero parece que este hermoso hecho no se descubrió hasta 1969. Mi prueba original de (20) se basaba en un teorema demostrado por el matemático soviético N. Vorob'ev en 1942, pero publicado sólo en la tercera edición argumentada (sic) de su popular libro [sobre la secuencia de Fibonacci]... Estudié la nueva edición del libro de Vorob'ev en el verano de 1969 y ese teorema me llamó la atención de inmediato. En aquel momento no deduje (20), pero después de leer el artículo de Julia Robinson vi inmediatamente que el teorema de Vorob'ev podía ser muy útil. Julia Robinson no vio la tercera edición del libro de Vorob'ev hasta que recibió un ejemplar mío en 1970. ¿Quién puede saber qué habría pasado si Vorob'ev hubiera incluido su teorema en la primera edición de su libro? Tal vez, el décimo problema de Hilbert habría quedado "sin resolver" una década antes".

Answer 5

Dos fórmulas que relacionan $\pi$ y la secuencia de Fibonacci.

$$\pi=\lim\limits_{n\to\infty}\sqrt{\frac{6\cdot \ln (F_1\cdot F_2\dots F_n)}{\ln(\mbox{lcm}(F_1,\dots,F_n))}},\qquad\qquad\qquad\qquad(1)$$ donde $\mbox{lcm}$ denota el mínimo común múltiplo.

$$\pi=4\ \sum\limits_{k=1}^{\infty} \arctan{(1/F_{2n+1})}\qquad\qquad\qquad\qquad\qquad\quad(2)$$

$(1)$ admite una demostración más bien elemental que se basa en las propiedades estándar de la función totiente de Euler. $(2)$ es casi trivial; se deduce de la identidad $$\arctan{(1/F_{2n+1})}=\arctan{(1/F_{2n})}-\arctan{(1/F_{2n+2})}.$$

Las relaciones se encuentran en "Una nueva fórmula para $\pi$ " de Matiyasevich y Guy (Amer. Math. Monthly 93 (1986), 631-635).