¿Es cierto que la secuencia de Fibonacci los restos cuando divide repitiendo 3?

Question

Sobre esta secuencia de Fibonacci, es cierto que los restos al dividir por tres repetición junto con la secuencia como esta:

Secuencia de Fibonacci:

$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946\cdots$

Resto cuando dividido por $3$ secuencia:

$1, 1, 2, 0, 2, 2, 01, 00, 01, 01, 02, 000, 002, 002, 001, 000, 0001, 0001, 0002, 0000, 00002\cdots$

Hice cada uno el mismo número de dígitos para alinearlos para evitar confusiones. ¿Es cierto que sucede cada ocho números? ¿Si es así, cómo y por qué esto sucede?

Answer 1

Una secuencia como la secuencia de Fibonacci está totalmente determinado por cualquiera de sus segmentos de longitud $2$. Modulo cualquier número $N$ (no sólo de $3$) hay sólo un número finito de segmentos posibles de la longitud de la $2$, de hecho hay $N^2$ de ellos, por lo que la secuencia de restos eventualmente se repite a sí misma y convertirse en los periódicos.

E. g.

• modulo $5$ : $0$, $1$, $1$, $2$, $3$, $0$, $3$, $3$, $1$, $4$, $0$, $4$, $4$, $3$, $2$, $0$, $2$, $2$, $4$, $1$, $0$, $1$, ... (volví a la $0$, $1$ segmento);

• modulo $7$ : $0$, $1$, $1$, $2$, $3$, $5$, $1$, $6$, $0$, $6$, $6$, $5$, $4$, $2$, $6$, $1$, $0$, $1$, ... (volví a la $0$, $1$ segmento de nuevo).

Se trata de un interesante "ejercicio" para calcular la longitud del período de la secuencia modulo de un primer $p$ sin llegar a la informática de toda la secuencia.

Answer 2

Se tiene que repetir. Los dos términos de la recursividad $$F_n=F_{n-1}+F_{n-2}$$ los rendimientos de la misma recursividad modulo $3$ de su secuencia modificada: $$f_n=f_{n-1}+f_{n-2}\mod 3$$ Cada uno de los valores sólo pueden tomar en $3$ valores distintos, por lo que hay en la mayoría de las $9$ diferentes combinaciones de $f_{n-1}$$f_{n-2}$. Se tiene que repetir después de que en la mayoría de las $9$ pasos para cualquiera de los dos término de recursión (no solo la de arriba), pero para algunos, incluso se puede repetir antes de que.

Puedes dibujar tú mismo un $3\times 3$ tabla y trace la ruta de acceso de la secuencia de ($f_{n-1}$,$f_{n-2}$) toma. Va como (1,1), (1,2), (2,0), (0,2), (2,2), (2,1), (1,0), (0,1)...

Usted ver que $(0,0)$ no es visitado.

Answer 3

Desde $f(n)=f(n-1)+f(n-2)$ el resto al dividir por tres de $f_n$ puede obtenerse conociendo el resto de los otros dos números.

Sólo se demostró que la secuencia comienza $1,1,2,0,2,2,1,0,1,1$ después de esto que tenemos que hacer exactamente la misma deducción que hicimos al principio. Por lo tanto ciclo.

Answer 4

El método de la ecuación característica también funciona el modulo $3$. Considere la posibilidad de $$ x^2-x-1 $$ en los tres elemento de campo $\mathbb{F}_3$. Este polinomio no tiene raíces, porque la fórmula cuadrática requiere de $\sqrt{5}=\sqrt{-1}$; si añadimos un elemento $i$ tal que $i^2=-1$, la extensión de campo en el que el polinomio se divide es lo $\mathbb{F}_3[i]$. Las raíces del polinomio son entonces $$ \frac{1+i}{2}=-1-i,\qquad \frac{1-me}{2}=-1+i $$ y la solución general de la ecuación de recurrencia es $$ \alpha(-1-i)^n+\beta(-1+i)^n $$ donde $\alpha,\beta\in\mathbb{F}_3$. Establecimiento $F_0=0$ $F_1=1$ da $$ \alpha=-i,\qquad \beta=i $$ y por tanto, los términos de la secuencia de Fibonacci modulo $3$ $$ i(-1+i)^n-i(-1-i)^n $$ En un campo con $9$ elementos tales como $\mathbb{F}_3$ tenemos $z^8=1$ para todos los elementos de la $z\ne0$, por lo que la secuencia se repita con el período de $8$. No menos, porque las otras posibles período se $4$, que no lo es.

Más generalmente, si el polinomio se divide en $\mathbb{F}_p$ ($p$ un prime de $2$$5$), el período será de $p-1$; si no de división, el plazo es de $p^2-1$.

El caso de $p=2$ pueden ser tratados con la incorporación de un elemento $j$ tal que $j^2+j+1=0$ (el período es $3=2^2-1$). En el caso de $p=5$ la ecuación característica tiene una raíz repetida $3$, por lo que la solución general es de la forma $$ \alpha\cdot 3^n+\beta\cdot n3^n $$ y el término general de la secuencia de Fibonacci modulo $5$$2n3^n$: $$ 0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,\dotsc $$ que tiene plazo,$20$. De hecho, con el fin de tener $2(n+k)3^{n+k}=2n3^n$ todos los $n$ necesitamos $(n+k)3^k=n$ todos los $n$. Para $n=0$ esto da $k3^k=0$, lo $k$ es divisible por $5$; $n=1$ esto da $(1+k)3^k=1$. Establecimiento $k=5h$ y recordando que $3^5\equiv 3\pmod{5}$, esto se convierte en $3^h=1$ y el menos positivo de la solución para esto es $h=4$.

Answer 5

Considerar que el % de pares $(R_k,R_{k+1})$$R_k$es el resto de $F_k$ al dividir por $3$. Puesto que hay infinitamente muchos tales pares, por principio de Pingeonhole existe $k,l$ tal que $(R_k,R_{k+1})=(R_l,R_{l+1})$. Así $R_{k-1}=R_{l-1}$ y así sucesivamente. Así que los restos son periódicos.

La misma propiedad es verdadera para toda secuencia con recurrencia lineal (con el mismo método).