La prueba de que la Secuencia de Fibonacci modulo m es periódica?

Question

Es bien sabido que la secuencia de Fibonacci modulo m (donde m es cualquier entero) es periódica. He descubierto una prueba de esto, pero al buscar en google, he encontrado pruebas en línea que eran mucho más complicado. Esto me lleva a sospechar que mi prueba puede ser falaz - que es la razón por la que estoy publicando aquí.

Prueba:

Nos deja una lista de la secuencia de Fibonacci modulo m, donde m es un número entero. Es algo parecido a esto en primer lugar (para 10 por lo menos):

1 1 2 3 5 8 3 1 4 5 9 4 3 7 ...

Obviamente, cualquier número en la secuencia es la suma de los dos últimos números del modulo m. Por lo tanto, si en algún punto de la serie del modulo m un par de números de la repetición, los números después de que la pareja debe repetir así. por ejemplo. si en algún momento vemos que el par 1, 1, 2, 3, 5, ... debemos seguir ese par.

Ahora hay m^2 posibles pares en la serie del modulo m. Por el principio del palomar, después de la m^2 + 1 términos, una pareja debe repetir. Si una pareja se repite una vez, se debe repetir de nuevo el mismo número de términos más tarde. Por lo tanto, la secuencia de Fibonacci modulo m es periódica para todo m.

Es mi prueba correcta?

Answer 1

No, no se ha demostrado aún que la secuencia de Fibonacci es periódica ($\exists t, \forall n, F(n+t) = F(n)$), que han demostrado que es finalmente periódico ($\exists t, \exists n, \forall m, m \ge n \implies F(m+t) = F(m)$)

Si usted tiene un conjunto finito $S$ (aquí, el conjunto de pares modulo $m$) y una función de $f :S \to S$, cualquier secuencia obtenida por recorrer $f$ sobre algún elemento de $S$ es el tiempo de periódico, por el principio del palomar. Si desea que todos los dichos de la secuencia de periódico, usted necesita $f$ a ser un bijection :

Si $f$ es un bijection y $F(n+1+t) = F(n+1)$ algunos $n$, luego mediante la aplicación de $f^{-1}$ obtenemos $F(n+t) = F(n)$, y volvemos a repetir hasta la obtención de $F(t) = F(0)$.

Si $f$ no es bijective, no es surjective, así que si usted comienza su secuencia en algún elemento no en la imagen de $f$, nunca será periódica debido a que este elemento no puede aparecer de nuevo en la secuencia.

Aquí, $f(a,b) = (b,a+b)$, que es un bijection porque su inversa está dada por $f^{-1}(a,b) = (b-a,a)$