¿Pregunta no trivial sobre números de Fibonacci?

Question

Estoy buscando un trivial, pero no es super difícil cuestión relativa a los números de Fibonacci. Debe estar en un nivel adecuado para un curso de licenciatura.

Aquí está una (no tan bueno) ejemplo de la clase de cosas que estoy buscando.

a) Probar que todo entero positivo se puede representar en binario sobre la base de los números de Fibonacci. Es decir, mostrar que para todo $n$, existen los bits de $x_1,\ldots,x_k$ tales que $n = \sum_{i=1}^kx_iF_i$.

b) Dar un algoritmo para incrementar esos números en constante amortizado en el tiempo.

Todas las ideas para mejor?

Answer 1

Aquí tienes algunos de los mejores que he escuchado:

1) Vamos a $a$ ser un entero positivo. Entonces $a$ es un número de Fibonacci si y sólo si al menos uno de los miembros del conjunto {$5a^{2}-4, 5a^{2}+4$} es un cuadrado perfecto.

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

2) Dejar que $\phi$ denotar el de Euler totient función. Demostrar que $\phi(F_{n}) \equiv 0 \pmod{4}$ si $n \geq 5$.

La prueba consiste en una inesperada de la aplicación de Lagrange del teorema de la Teoría de grupos. Supongo que hay algunas otras maneras de demostrarlo, pero que el enfoque siempre será mi taza de té. El problema fue planteado y resuelto en el Mensual en los años 70 (si mi memoria no me falla, a la derecha). Busca todas las entradas por Clark Kimberling en la revista, y de seguro lo encontrarás.

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

Este problema sería trivial si en lugar de los $\cdot$ le había colocado un signo más que hay. En cualquier caso, no hay necesidad de pánico con esta propuesta. Todo lo que usted necesita recordar es el correspondiente primitiva divisor teorema.

4) Ben Linowitz se mencionó anteriormente un bello resultado por el Profesor Florian Luca, a saber:

No hay ninguna perfecta números en la secuencia de Fibonacci.

Leí el artículo en mi primer año y no me pareció difícil de seguir. La parte fácil de este lindo nota reside en la prueba del hecho de que no hay ninguna perfecto números en la secuencia de Fibonacci. Supongo que este resultado es lo suficientemente interesante como para merecer la consideración de esas charlas que usted tiene la intención de dar. Si esta propuesta no es exactamente su idea de la emoción, puede echar un vistazo a algunos de los otros papeles por el Profesor Florian. Él escribe mucho acerca de la recurrencia de las secuencias. Otro teorema de la suya, estrechamente relacionada con el tema de esta discusión, establece que

No es que no abelian finito simple grupo cuyo orden es 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 utilizar este hecho para derivar la continuación de la fracción para el desarrollo de la proporción áurea.

Esta debe ser bien conocido, sin embargo, sería bueno para ver lo que sus estudiantes vienen con...

Añadido (Nov 20/2010) acabo de notar que el Fibonacci Assn. ha puesto a disposición de los artículos publicados en La serie Trimestral entre 1963 y 2003. Estoy seguro de que usted va a encontrar un montón de material adicional entre los archivos que tan generosamente liberado para nuestro disfrute. Por ejemplo, el trabajo seminal de J. H. E. Cohn que K. Ratonero menciona a continuación puede encontrar aquí.

Answer 2

Accesible (y muy interesante) lo que hay que mirar con los números de Fibonacci es su periodicidad modulo varios enteros, especialmente de los números primos y el primer poderes. Un ejemplo de un sencillo resultado es que, si $k(p)$ es el período de los números de Fibonacci modulo de un primer $p$, entonces $k(p)\mediados de p^2-1$. Usted puede obtener resultados más definidos mediante el examen de si o no 5 es una ecuación cuadrática de residuos mod $p$ (pensar en la importancia de $\frac{1\pm\sqrt{5}}{2}$ para los números de Fibonacci). Usted puede probar cosas acerca de esta periodicidad directamente, o reducir la matriz 2x2 que Gowers menciona modulo $p$ y obtener la misma cosa, dependiendo de lo que te gustaría destacar a tus 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 clara acerca de los números de Fibonacci es su apariencia como las sumas de las "diagonales" en el Triángulo de Pascal, como en esta imagen:

Sin embargo, este hecho es comprobable simplemente por inducción, así que tal vez esto es demasiado fácil de lo que usted tiene en mente.

Answer 3

En 1964 J. H. E. Cohn probó que la plaza más grande de la secuencia de Fibonacci era 144. La prueba utiliza datos estándar sobre plazas mod $p$, incluyendo la reciprocidad cuadrática, de forma ingeniosa. Es MR0163867 en matemáticas comentarios si quiere perseguir esto para arriba. Esta es una de las pruebas que puede leer y entender fácilmente, pero sería un diablo para descubrirse a uno mismo. He dado este problema a los estudiantes como un ejercicio muy largo con toques.

Answer 4

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

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

En 1992 en la edición de Otoño de el Anticuario había una nota por Matiyasevich donde explicó, entre otras cosas, la importancia de que la relación en su trabajo sobre Hilbert del décimo problema. Aquí tienes un extracto de la nota:

"No es difícil demostrar esta notable propiedad de los números de Fibonacci después de que se ha dicho, pero parece que este hermoso hecho no fue descubierto hasta el año 1969. Mi original de la prueba de (20) se basa en un teorema demostrado por el matemático Soviético N. Vorob'ev en 1942, pero publicado sólo en el tercer alegaciones por la (sic) de la edición de su popular libro [en la secuencia de Fibonacci]... estudié la nueva edición de Vorob'ev libro en el verano de 1969 y que el teorema de la atrajo mi atención de inmediato. Yo no deducir (20) en ese momento, pero después de leer Julia Robinson papel inmediatamente vi que Vorob'ev del teorema puede ser muy útil. Julia Robinson no ver la tercera edición de Vorob'ev del libro hasta que recibió una copia de mí en 1970. Quién puede decir lo que habría sucedido si Vorob'ev había incluido su teorema en la primera edición de su libro? Tal vez, Hilbert del décimo problema habría sido "sin resolver" una década antes!"

Answer 5

Dos fórmulas relativas $\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 mayoría de los de primaria prueba que se basa en las propiedades estándar de Euler totient función. $(2)$ es casi trivial; de ello se deduce a partir de la identidad $$\arctan{(1/F_{2n+1})}=\arctan{(1/F_{2n})}-\arctan{(1/F_{2n+2})}.$$

Las relaciones se pueden encontrar en "Una nueva fórmula para $\pi$" por Matiyasevich y Guy (Amer. De matemáticas. Mensual 93 (1986), la 631-635).