Hacer y probar una conjetura acerca de cuando la secuencia de Fibonacci, $F_n$, es divisible por $7$.
Me he dado cuenta de que es al $n$ es un múltiplo de a $8$. Yo no sé cómo ir sobre la prueba.
Respuestas
¿Demasiados anuncios?
Goofy
Puntos
119
Mira la secuencia de $F_n$ de reducción de mod $7$:
1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0, 1,1,2.. and it repeats forever
Ya que los únicos lugares donde es 0 se $n=8,16$ esto demuestra que $7|F_n \iff 8|n$.
Teoría General de las relaciones de recurrencia.
Definición de Un $k$th el fin de la recurrencia de la relación en un conjunto $X$ es una función de $a : \mathbb N \rightarrow X$ $k$ valores iniciales decir $a(1),\cdots,a(k)$ definido y para todos $i > k$, $a(i+k+1) = f(a(i),a(i+1),\cdots,a(i+k))$. Tenga en cuenta que un $k$th el fin de recurrencia es también una $k+1$th el fin de recurrencia.
La notación Nos suelen escribir los elementos de una $k$th el fin de la recurrencia de la relación como $(a_n)$.
Definición de la Recurrencia de la relación homomorphisms, vamos a $(a_n)$ $k$th el fin de la recurrencia de la relación en el conjunto de $X$ definido por el mapa $f : X^k \rightarrow X$ (así como de algunos valores iniciales). Un mapa de $\varphi : X -> Y$ se llama recurrencia relación homomorphism en $a$ cuando no existe $f' : Y^k \rightarrow Y$ la satisfacción de las conmutativo el diagrama de $\varphi \circ f = f' \circ \varphi$.
Teorema de la Recurrencia de la relación homomorphisms producir relaciones de recurrencia. Supongamos que tenemos una relación de recurrencia homomorphism en la notación anterior. El reclamo es que el $b_n = \varphi(a_n)$ $k$th el fin de la recurrencia de la relación.
Prueba Claramente $k$ inicial de los valores, más allá de $i > k$ tenemos $b_{i+k+1} = \varphi(f(a_{i},a_{i+1},\cdots,a_{i+k})) = f'(\varphi(a_{i}),\varphi(a_{i+1}),\cdots,\varphi(a_{i+k}))) = f'(b_{i},b_{i+1},\cdots,b_{i+k}).$
Ejemplo La "reducción de la mod m" mapa de $\varphi : \mathbb Z \rightarrow \mathbb Z/m\mathbb Z$ como se describe aquí es una recurrencia homomorphism en cualquier recurrencia definida por un polinomio. Para ver esta nota que homomorphisms de los anillos (como $\varphi$) pueden ser elevados a homomorphisms en el polinomio de anillos de los respectivos anillos. Que induce el mapa de$f$$f'$.
Ejemplo de Llamada de la secuencia de Fibonacci $(F_n)$ de reducción de la mod 7: $(S_n)$, esta es una recurrencia por el ejemplo de arriba. Tenga en cuenta que $F_n \equiv S_n \pmod 7$.
Teorema de los segmentos Inicial puede ser descartada. Supongamos $a_n$ es una recurrencia de la relación de orden $k$, $b_n = a_{n+h}$ para cualquier constante $h$ es también una recurrencia de la relación de orden $k$.
La prueba Inicial de valores se calculan fácilmente, si $f$ es la función de los elementos definitorios de $a$ $f$ también define los elementos de $b$, a ver esta nota, que para $i > k$ tenemos $b_i = a_{i+h} = f(a_{i+h},a_{i+1+h},\cdots,a_{i+k+h}) = f(b_{i},b_{i+1},\cdots,b_{i+k})$.
Teorema De Periodicidad. Suponga que la relación de recurrencia $b_n$ se define como $a_{n+h}$ (ambos de $k$th orden), si comparten la primera $k$ valores iniciales, a continuación, son iguales en todas partes.
La prueba de Inducción en $n$ en los más fuertes de la proposición de que para todos los $i \le n$, $a_i = b_i$.
caso base (n = k): Esta es la hipótesis del teorema.
paso recursivo ($n \implies n+1$): Puesto que para cada $i \le n$, $a_i = b_i$ tenemos $a_{n+1} = f(a_{n-k},a_{n-k+1},\cdots,a_{n}) = f(b_{n-k},b_{n-k+1},\cdots,b_{n}) = b_{n+1}$ (ya que ambos son definidos por $f$).
Ejemplo Definir $S'_n = S_{n+16}$ comparten los dos primeros valores iniciales por lo tanto son iguales en todas partes.
Ejemplo Definir $S_n^r = S_{n+16\cdot r}$ por inducción estas son todas iguales: El caso base $r=0$ es trivial y el paso recursivo $r \implies r+1$ viene de una adaptación del ejemplo anterior y la transitividad.
Teorema $7|F_n \iff 8|n$.
Prueba Por los ejemplos anteriores hemos visto que $F_n \equiv F_{n+16\cdot r} \pmod 7$, además de un cálculo directo de los primeros 16 valores de $S_n$ (en la parte superior) muestra que $F_n \equiv 0 \pmod 7 \iff n = 0+16 \cdot r,8+16\cdot r$ esto es equivalente a $8|n$ $x = 0 \pmod m$ es equivalente a $m|x$.
Oded
Puntos
271275
Una de peatones más enfoque de inducción, mirando a los primeros 16 números de fibonacci, sólo el 2 que son divisibles por 7$f_8=21$$f_{16}=987$. Conjetura de que $f_n$ es divisible por 7 si y sólo si $n$ es divisible por 8, como usted menciona en los comentarios. El uso de estas observaciones como en el caso base, se asume que el resultado se mantiene para todos los $f_j$$j\leq n$. Aviso
$$ f_{n+1}=21f_{n-6}+13f_{n-7} $$
que pueden ser resueltos por la aplicación continua de la definición recursiva de la secuencia de fibonacci. Esta ecuación hace que la inducción de seguir con bastante facilidad.
David HAust
Puntos
2696
Sugerencia $\ $ Considera que el cambio de mapa $\rm\:n\to n+1\:$ en los pares de $\rm\:(f_{n-1},\:f_n)\,\ \ (mod\ 7)\:.$ a Continuación es una sugerencia de uno de mis viejos sci.matemáticas puestos. Ver esta respuesta para mucho más.
> A sequence f(n) satisfies the relation f(n+2) = [f(n+1)]^2 - f(n),
> with f(1) = 39 and f(2) = 45. Prove that 1986 divides infinitely
> many terms of the sequence.
Desde la recursividad determina los valores únicos de $\rm\:f_{n+2},\:f_n\:$ cuando correr delante hacia atrás, el cambio de mapa en la secuencia induce una permutación $\rm\:F\:$ de enteros pares $$\rm mod\ 1986\!:\ \ F(f_n,f_{n+1})\ =\ (f_{n+1},f_{n+2})\ \quad i.e.\quad F(a,b)\: =\ (b,\,b^2-a)\ \ $$ Pero $\:0\:$ se produce en el ciclo que contiene a $(39,45)$ desde $\rm\:F(39,45)\: =\: (45,0),\:$ por lo $\:0\:$ se produce infinitamente a menudo en este ciclo finito al $\rm\:F\:$ es iterado.
Esto reemplaza menos formal de los argumentos de la otra parte en "repetidas de bloques" por los argumentos rigurosos en estructuras estándar (permutaciones y su ciclo de descomposición), por lo tanto el esclarecimiento de la esencia de la cuestión. Uno debe esforzarse para aprender a reconocer estas abstracciones en la naturaleza, otra cosa será condenado continuamente reinventar la rueda (aquí ciclo).
user3014219
Puntos
1
Hay una cosa fría con la de Fibonacci y el número 7, se convierte en una secuencia de 16 número que se repite infinitamente.
0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0
Si sigues con la secuencia que usted puede ver que hay un 0 en cada 8ª posición, de manera que esto nos deja con dos rebanadas de secuencia.
s1 : 1,1,2,3,5,1,6 s2 : 6,6,5,4,2,6,1
Así finobacci en el módulo 7: 0s10s20s10s2........
Si usted toma una consecutivos s1 , s2 y agregarlos número por número:
s1 : 1,1,2,3,5,1,6
s2 : 6,6,5,4,2,6,1 +
7,7,7,7,7,7,7
Que en el módulo 7 es 0, por lo Fibonacci se transforma en una secuencia infinita de 0.
Así, el proceso será el siguiente: 1. Módulo 7 a la secuencia de Fibonacci.
0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0....
El grupo de ellos por grupos de 8 números.
Si usted toma todos los grupos de s1 y agregar a ellos con sus respectivos s2, consecutivos. El resultado debe ser una secuencia infinita de 0.
