¿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

El siguiente ejercicio parece ser del tipo que estás buscando.

Dejemos que $F(x)$ sea la función generadora ordinaria de la sucesión de Fibonacci, es decir $$F(x) = \sum_{n=0}^\infty f_nx^n = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + \cdots$$ Demuestre que para todo $n \geq 0$ El $n$ -ésimo número de Fibonacci $f_n$ es igual a $$\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right].$$

Dependiendo de las capacidades de sus alumnos, puede orientarles pidiendo primero que demuestren que $F(x) = 1/(1-x-x^2)$ . La siguiente pista también puede ser útil: $1 - x - x^2 = \left(1 - \frac{1+\sqrt{5}}{2}x\right)\left(1 - \frac{1-\sqrt{5}}{2}x\right).$

Answer 2

Una conexión con la suma divergente.

Primero me sorprendió mucho que la suma alternada de todos los números de fibonacci resultara ser

$ 1-1+2-3+... = 1 \text{ \{Euler-summation\} } $

Pero bueno, a veces las cosas son fáciles, así que por qué no. Pero el no -la suma alternativa suele ser mucho más difícil de acceder. Pero no:

$ 1+1+2+3+5+8+... = -1 \text{ \{matrix-sum\}} $

mediante un enfoque matricial, simplemente. Recientemente hubo un hilo en el grupo de noticias sci.math donde también se mostró esto. La discusión sobre esto se encuentra en Sitio de Rob Johnson - Finalmente, esto se puede demostrar utilizando la forma Binet de los números de fibonacci y considerando la serie geométrica, que resulta si se suman todos los números de fibonacci en su representación Binet.

Una vez que he experimentado con la suma (divergente) de los números de bernoulli, ponderada por los números de fibonacci. Todavía no pude demostrarlo, pero llegué al resultado muy probable de que esa suma es cero (Ver pg.11 de Bernoulli/Fib )

Answer 3

Los números Fibonacci consecutivos dan lugar al máximo número de iteraciones en el algoritmo GCD de Euclides en comparación con todos los pares menores.

Answer 4

Una identidad muy sencilla pero interesante es

$$f_{n+1} = \left[ \frac{1+\sqrt{5}}{2} f_n \right] ; n > > 0 \,.$$

donde $[ \; ]$ denota el número entero más cercano. Si recuerdo bien esta igualdad se mantiene para todos los $n >5$ y en general es cierto para todas las recurrencias para las que el último valor propio es un número de Pisot.

Answer 5

Aquí hay uno que surge en el análisis de los montones de Fibonacci, una estructura de datos en informática para llevar la cuenta del mínimo de un conjunto de elementos. Sin embargo, no hace falta saber nada de informática para entender el análisis:

Supongamos que un bosque dinámico de árboles enraizados sufre dos tipos de cambios:

• Si las raíces de dos árboles tienen el mismo número de hijos, pueden fusionarse haciendo que una raíz sea hija de la otra.
• Algunas aristas del árbol pueden ser eliminadas, haciendo que el nodo hijo de la arista sea promovido para convertirse en la raíz de otro árbol. Sin embargo, durante cualquier periodo de tiempo en el que cualquier nodo x no sea a su vez la raíz de uno de los árboles, como máximo uno de los hijos de x puede ser eliminado de esta manera.

Demuestre que, en el bosque resultante, cada nodo con n hijos tiene al menos $F_n$ nodos (incluido él mismo) en su subárbol, donde $F_n$ es el $n$ número de Fibonacci.

La recurrencia $$F_n = 2 +\sum_{i=0}^{n-2} F_i$$ (para $n>0$ ) que se obtiene como parte de la prueba no es la recurrencia estándar para los números de Fibonacci, sino que tiene la misma solución, como puede demostrarse fácilmente por inducción.