El problema de la semana trata sobre factores de los números de Fibonacci. Está inspirado en este post del blog de nuestro comentarista J.H.S. y en uno de los comentarios del mismo. Aprovecho para recomendar su blog por los problemas que plantea:
Consideramos los números de Fibonacci
denotados por
, con
, y sea
un número natural cualquiera mayor o igual que
.
1) Demostrar que existe un número de Fibonacci
.
2) Demostrar que existen infinitos números de Fibonacci que son múltiplos de
Vamos a por él.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Para el segundo item:
$latex F_n=F_{n-1}+F_{n-2}=2F_{n-1}+F_{n-2}=
3F_{n-1}+2F_{n-2}=5F_{n-1}+3F_{n-2}$, en general
Si tenemos
t.q. 
y así multiplicando el índice por dos vamos obteniendo más números de fibonacci múltiplos de 
entonces con la fórmula anterior tenemos
Vale, me he colado al pasarlo a LaTeX y en unos índices:
$latex F_n=F_{n-1}+F_{n-2}=2F_{n-2}+F_{n-3}=
=3F_{n-3}+2F_{n-4}=5F_{n-4}+3F_{n-5}$, en general
Y luego con
obtengo
Sí señor, Cristobal. Esa es la idea para demostrar 2).
Los números de Fibonacci verifican la importante propiedad
(que se demuestra fácilmente por inducción, en la línea que comentas) y que, en particular, muestra que todos los números 
son múltiplos de 
(y por tanto de 
).
Ahora a por la 1)
La secuencia de los números de Fibonacci puede empezar desde F(0)=0. Por ejemplo:
0,1,1,2,3,5,8,13…
Cuando la secuencia se toma desde F(1)=1 se los denomina «Números Fibonacci positivos» (Positive Fibonacci numbers) o sino «Números de la espiral de Fibonacci» (Fibonacci´s spiral numbers).
sí, pero por unificar criterios ponemos
y a partir de ahí se sigue con el criterio. El problema va referido a este caso.
Para rellenar estos días de asueto les propongo, al tiempo que se resuelve la cuestión pendiente, analizar la convergencia de la serie siguiente
donde
es un número real positivo y 
es la sucesión de Fibonacci (con 
). ¿Converge la serie para todo valor de 
? Si no es así, ¿Cuál es el mayor valor de 
para el que la serie diverge?
Hola, he hecho la función generatriz de la serie que has escrito utilizando la recurrencia de la sucesión de Fibonacci, y queda a/(a^(2)-a-1), que es positivo si y sólo si a es estrictamente mayor que el número áureo y converge en este caso, a su vez es negativa o queda nulo el denominador si y sólo si a pertenece a (0, fi], entonces la respuesta sería fi, me equivoco?
Hola, el otro día me plantearon una cuestión.
No se donde ponerla, así que la dejare aquí planteada.
Como demostrar que:
Bueno, lo que quiero poner era esto, que creo que era lo mismo.
Me han dicho que no es tan fácil de demostrar como parece.
Lo he intentado por inducción, y sustituyendo con la expresión
y no he llegado a ningún lugar.
Hay alguna otra propiedad de los números combinatorios que se pueda utilizar?
Masterateo:
,
con 
como coeficiente de 
.
es
Se me ocurre desarrollar el polinomio
por un lado es igual a
Por otro lado es
$latex ((1+x)^n)^2=
\left(\sum_{k=0}^n\binom{n}{k}x^k\right)^2=
\sum_{k=0}^n\sum_{j=0}^n\binom{n}{k}\binom{n}{j}x^{k+j}$
cuyo coeficiente de
$latex \sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}=
\sum_{k=0}^n\binom{n}{k}^2$
Desarrollándo la serie módulo m, el número de posibles valores para F(n) es finito e igual a m. El número de pares posibles [F(n), F(n+1)] tambien es finito, concretamente hay m^2 pares posibles. Por tanto la serie que se obtiene es periódica, porque tarde o temprano se tiene que repetir un par y seguirá igual a partir de ahí. Además, el periodo empieza ya en F(1), ya que dado un par cualquiera [F(n), F(n+1)] se puede calcular sin ambigüedad tanto F(n-1) como F(n-2). Sólo hay un camino en la serie para llegar a [F(n), F(n+1)]. Además, si a partir de… Lee más »
Masterateo, muy interesante propiedad la que propones. Conozco la siguiente prueba:
Comenzamos con la identidad
, para 
. Haciendo el desarrollo de las potencias en términos de los números combinatorios, multiplicando las sumas que aparecen en el primer miembro, e igualando coeficientes, obtenemos que
$latex \displaystyle{\sum_{i=0}^{min\{k,n\}} \binom{n}{i}\cdot\binom{m-n}{k-i}}=\binom{m}{k},\quad
k=0,\ldots,m$.
Finalmente toma
y 
, y llegas al resultado teniendo en cuenta la simetría de los números combinatorios.
Perdón, al final se me coló un 1 de más (o un -1 de menos). Rectificado el fallo quedaría así:
(n+1)<(m-1)^2
n < m^2 – 2m < m^2
Saludos!
Muy buena, Sive!!
Nos queda estudiar la suma (que es muchísimo más sencillo).
Jeje, en realidad cometí otro fallo, me dejé otro 1 en el limbo. Pero bueno, tengo 2m de margen 😛
Propongo intentar acotar aún más el problema 1), para que n esté entre 1 y 2m.
Vaya día tengo, el problema que propongo, esta vez sin ambigüedades es:
Consideramos los números de Fibonacci
denotados por 
, con 
, y sea m un número natural cualquiera mayor o igual que 
Demostrar que existe un número de Fibonacci
múltiplo de 
de tal modo que 
Buenas, alguno conoceis algun libro de sucesiones numericas, si es asi, si podeis decirme el titulo se agradece, muchas gracias,
Muy interesante la nueva acotación, Sive. Dicha cota para
es la mejor que se puede dar, ya que se cumple exactamente para 
.
quise decir
Hm, estuve pensando en el dia como demostrar la A, sin llegar a buen puerto, pero usando la parte A la parte B se me hacia directa, pues (con la cota antigua) sabemos que para cada m hay un numero con indice menor q m^2 , luego basta notar q para m^n en general hay un numero en la serie antes del m^2n -ésimo , con esto encontramos infinitos multiplos de m dentro de la serie…es directo «maquillar» la solucion para la nueva cota. Espero se entienda… con respecto a lo q se propone de la suma de los cuadrados… Lee más »
He logrado demostrar que la cota es
cuando 
es primo, y que la cota es 
cuando 
se puede descomponer en factores primos con potencia 1.
Ahora intento demostrar el caso para cuando
, siendo 
primo, y expero poder usar el resultado para cualquier 
.
Me lo estoy pasando bomba, la verdad.
Sive, interesante teorema el que planteas. No sé si habrá una demostración directa, pero se deduce de los siguientes resultados de la teoría de las sucesiones de Fibonacci módulo m :
Si
es el índice mínimo tal que 
es múltiplo de m y 
es la descomposición de m en primos,
Usando estas proposiciones se obtiene que
es máximo solo cuando 
y en ese caso 
.
estupendo, Sive, efectivamente para primos el índice óptimo es p+1. Podrías indicarnos tu razonamiento?
fede, conoces algún link o cualquier referencia donde vengan demostradas esas cinco identidades? El otro día me tropecé con ellas pero no he visto demostración.
Con unas propiedades análogas a las que indica fede, parece que se puede probar que el periodo de la sucesión de Fibonacci módulo m, se reduce a 6m, lo cual mejora (para
) la cota 
que aparece en el planteamiento inicial.
Pues esas proposiciones están muy en la onda del camino que yo he elegido para encontrar una demostración.
De hecho lo que ahora pretendo demostrar, usando tu nomenclatura es que:
¿Sabes si están demostradas en el enlace que has puesto?
Realmente no he leido en detalle la documentación pero los números de teoremas del enlace anterior que dan lugar a los resultados (1)-(5) son: (1) 3.30 (2) 3.5, 3.25 (3) y (5) 3.8, 3.12, 3.13, 3.25 (4) 3.7, 3.25 3.32 Creo que no es autocontenido por el lema 3.6, para el que remite al libro de Vajda (que acaba de reeditarse). Otro artículo interesante es http://citeseer.ist.psu.edu/555843.html Y para el tema de la cota 6m para la longitud del ciclo http://www.mathpages.com/home/kmath078.htm y http://arxiv.org/abs/cs.OH/0512103 En N.N.Vorobiov «Numeros de Fibonacci», Editorial MIR, Lecciones populares de matemáticas, pag 55, hay un resultado que quizá… Lee más »
Demostraré que la cota es , cuando es primo. Definamos como la serie: Es decir, como la serie de Fibonacci pero comenzando en en lugar de . La serie de Fibonacci, con esta nomenclatura, sería . Es fácil comprobar que es posible obtener la serie multiplicando cada elemento de por . Es decir: (1) A partir de aquí trabajamos en módulo . Módulo , hay series diferentes, desde hasta . Es decir, De (1) se deduce que, salvo para , los ceros en están en la misma posición que los de , ya que sólo si o son 0. Como… Lee más »
Donde puse: Llamemos al periodo con que aparecen los ceros en . Cualquier par de elementos consecutivos contenido en esos elementos de , no puede estar en los primeros elementos de otra serie , porque de darse el caso la serie continuaría igual hacia atrás y tendríamos que . Debí poner (en mayúsculas la errata): Llamemos al periodo con que aparecen los ceros en . Cualquier par de elementos consecutivos contenido en LOS PRIMEROS elementos de , no puede estar en los primeros elementos de otra serie , porque de darse el caso la serie continuaría igual hacia atrás y… Lee más »
Creo que di un salto no demasiado obvio al final, cuando puse:
Lo aclaro por si acaso.
El número de pares posibles que tienen disponibles cada una de las series
con 0<a<m es igual al número total de pares salvo 
que no está en ninguna de ellas, dividido entre el número de series 
. Y de ahí, la fórmula.
Una pregunta … ¿como se expresaría 0<a<m en latex?
Buen trabajo, Sive.
) y \succ (
).
Debido a problemas a la hora de visualizar mayor que y menor que (al parecer los confunde con etiquetas html) utilizamos \prec (
Gracias Asier 🙂 Una curiosidad. No he demostrado (ni lo haré, porque no es cierto) que cualquier par imaginable está en algún . De hecho, para m=5, hay 4 series con z=5. Con lo que tenemos 4·5 = 20 pares, 5 menos que los 25 posibles. Esto es porque, además del (0, 0), los los 4 pares (3,4), (4,2), (2,1) y (1,3) tampoco se dan nunca. Curiosamente, estos cuatro pares se pueden unir en una pseudo-serie de Fibonacci así: 3,4,2,1,3,4,2,1,… No es casualidad, es fácil de demostrar que con los pares sobrantes se pueden formar 1 o más pseudo-series de… Lee más »
Disculpándome por anticipado por la ignorancia y con el permiso de todos, quiero mostrar un sencillo teorema en el que estuve pensando, referido a divisores y múltiplos, pues quisiera tener alguna referencia del mismo. El teorema dice así: El número de divisores de «n» que son múltiplos de «m» es igual al número de divisores de (n/m) si y solo si (n/m) es entero, en caso contrario es igual a cero. He notado que la secuencia se forma utilizando los términos de la función divisor d(n) intercalados entre m-1 ceros. Por ejemplo para m=1 la secuencia es: 1,2,2,3,2,4,2…. Si ahora… Lee más »
Sive, quería darte las gracias por indicar tus razonamientos y también felicitarte por cómo lo has demostrado. Me parece una demostración preciosa!
Ejemplo: n=33550336, m=524224. El número de divisores de 33550336 que son múltiplos de 524224 es igual al número de divisores de 64, es decir 7. Pues d(33550336/524224)=d(64)=7.
De nada, Domingo 🙂 ha sido un placer.
Y… ya he demostrado lo que me faltaba. Esto no me ha gustado, porque era una estupidez comparado con lo anterior, me ha sentado muy mal no haberlo visto antes.
Tengo que salir, a la vuelta intento exponerlo todo.
Sive, usando la phi de Euler he visto muy fácilmente con tu mismo desarrollo que
para potencias de primos. Me falta mirar el caso general de productos de potencias…
Pues es posible que ese camino también lleve al mismo resultado Domingo, pero ya sabes como es esto, uno se encuentra ante varias posibilidades y tiene que probarlas una a una, sin más orientación que la intuición (que para nosotros los pobres mortales, no es demasiado fiable).
El producto de potencias se puede abordar con la proposicion (1) de las que puso Fede, que es fácil de demostrar, pero necesitarias acotar un poco más ese
Voy a demostrar que los ceros módulo de la serie de Fibonacci aparecen periódicamente y están uniformemente repartidos. Es decir que todos los ceros se pueden expresar como , siendo el primer valor de para el cual da cero, y es cualquier entero positivo. Es fundamental para poder generalizar la cota de para cualquier . Sabemos que: sigue siendo el primer valor de para el cual da cero, y es un entero tal que (Asier 🙂 ). Supongamos que es cero: La única forma de que esto sea cierto es que sea cero, pero eso es imposible porque es menor… Lee más »
Muy buenas demostraciones, Sive 🙂
Propongo cambiar la notación de
. Se ve mejor.
Vaya, se me olvidó lo más importante, que es cómo afecta eso al problema que nos ocupa.
Supongamos que que queremos estudiar la periodicidad con que aparecen los ceros (porque ya sabemos que aparecen periodicamente), para
, bueno pues:
Cuando se cumpla que:
y
Siempre y cuando
y 
sean primos entre sí. Lo cual se resuelve directamente calculando el mínimo común múltiplo de los periodos módulo a, y módulo b. La explicación es la misma para 
siempre y cuando todos los factores sean primos entre sí.
Es la demostración de la proposición (1) de las que dijo fede.
De acuerdo Fede, para la próxima.
En cuanto a la serie planteada por Domingo, tenemos:
Despejando
obtenemos: 
La raíz positiva del denominador es justamente el número áureo:
Por lo tanto la serie diverge si
y converge para 
Tal vez mi demostración de que los ceros aparecen periodicamente para cualquier
requiera una aclaración adicional. Cuando escribí:
Supongamos que
es cero:
Y concluí que la única forma de que eso fuera cierto es que
sea cero, es porque 
no puede ser múltiplo ni de 
ni de ningún factor de 
, y por eso no importa que 
no sea primo.
Y
no puede ser múltiplo ni de 
ni de ningún factor de 
porque ya demostré previamente que los ceros para módulos primos son periódicos.
Lo siento Fede, lo volví a escribir con subíndices.
Asier, la respuesta a la suma propuesta es correcta. De todos modos, rigurosamente, ese camino no es del todo correcto para probar la divergencia para números menores o iguales que el número áureo. Supongamos que la serie hubiese sido con
directamente, ¿Por qué diverge? (de todos modos la respuesta es sencilla)
Bueno, indicar que obtuve la cota 2m usando que
(
es la función de Euler) si m es potencia de un primo, pero esto no me vale en general para otros números compuestos. Si m es primo el mismo desarrollo me da el p+1. A ver si podemos sacar la cota 2m en general sin usar ninguna propiedad no demostrada.
Mil gracias al Editor de Gaussianos por tomarse la molestia de voltear la mirada hacia la bitácora de un servidor suyo. 🙂 Gracias a todos los que han sido partícipes del thread. Domingo: Concuerdo contigo con respecto a la observación hecha sobre la última entrada de Asier. Se tiene que hacer un poco más de análisis por ahí. Atención Todos: Tenía la idea de ofrecer un premio a la primer respuesta satisfactoria al problema de convergencia planteado por nuestro amigo Domingo. Dado que la respuesta se encuentra libre (casi) en Gaussianos, no me queda más que anunciar que el premio… Lee más »
Domingo, ya veo que usando la indicatriz de Euler se demuestra que a(p^k) < 2p^k con el método de Sive.
Aunque no se llegue a más, ya me parece notable el resultado, demostrado de forma tan simple.
Por otro lado es fácil de demostrar, usando la identidad
, que se cumple para todo k, y las observaciones se Sive en su demostración, que en un ciclo completo (mod m) hay 1, 2 o 4 ceros o, en los términos de la demostración anterior, que está formado por 1, 2 o 4 bloques 
.
Cometí un fallo para mi demostración para
, me he dado cuenta al intentar explicarlo. Fue un fallo bastante tonto, lo cual quiere decir que he pasado demasiado tiempo pensando en esto…
Voy a hacer una pausa hasta mañana. Si puedo, porque cuando una cosa de estas se te mete en la cabeza…
Jeje, como me he propuesto no pensar en este problema más por hoy, me he puesto a investigar como escribir > y < en latex.
He aprovechado mi pausa para profundizar en vuestras ideas. Me ha encantado lo de los 1, 2 o 4 bloques Fede, eso se podría para usar la cota del periodo de F(n).
Y mañana lo mismo intento sacar algo en claro de la funcion de Euler, no creo que una demostración completa, pero al menos a ver si algo que me sirva.
Voy a acotar, por fin, para el caso de , siendo primo. Al final me he alegrado de haberme equivocado anteriormente porque esta demostración sí que merece el esfuerzo que he invertido en ella. Voy a definir como el periodo de los ceros en la serie de Fibonacci módulo . Es decir, ésta es la misma función que Fede llamó y definió como el índice mínimo tal que es múltiplo de , pero como ahora sabemos que los ceros aparecen periódicamente, prefiero hablar de «periodo» (de los ceros sólo, no de la serie completa) en lugar de «índice mínimo». (Le… Lee más »