El $ $(F_ {n}) de secuencia de números de Fibonacci se define por la relación de recurrencia
$$ F_ {n} = F_ {n-1} + F_ {n-2} $$ para todos $n \geq 2$ con $F_ {0}: = 0$ y $F_ {1}: = 1$.
Sin inducción matemática, ¿cómo puedo mostrar ese $$ F_ {n} \equiv F_ {n + 20} \pmod 5$ $ para todos $n \geq 2$?
En mod $5$,
$$ \begin{align}F_N & \equiv F_ {N-1} + F_ {N-2} \\ & \equiv F_ {N-2} + F_ {N-3} + F_ {N-3} + F_ {N-4} \\ & \equiv F_ {N-3} + F_ {N-4} + 2 (F_ {N-4} + F_ {N-5}) + F_ {N-4} \\ & \equiv F_ {N-4} + F_ {N-5} + F_ {N-4} + 2 (F_ {N-4} + F_ {N-5}) + F_ {N-4} \\ & \equiv 3F_ \end {N-5} {alinear} $$ por lo tanto, tenemos
$$ \begin{align}F_{n+20} & \equiv3F_{n+15}\\ & \equiv 3\cdot 3F_ {n + 10} \\ & \equiv 3\cdot 3\cdot 3F_ {n + 5} \\ & \equiv 3\cdot 3\cdot 3\cdot 3F_ {n} \\ & \equiv F_n\end {Alinee el} $$
Como un enfoque diferente, sólo se puede resolver exactamente el mod(5) de recursividad. Hay un pequeño problema en que la ecuación característica $$ \lambda^2=\lambda + 1$ $ tiene una raíz doble, 3, mod 5. Pero el dispositivo estándar, con $n\lambda ^ n$ trabajos y vemos que el término general, mod (5), es $$ F_n =(1+n) 3 ^ n$ $ entonces está pidiendo que $(1+n) 3 ^ n = (1 + n + 20) 3 ^ {n + 20} $ mod (5). Pero 21 + n = 1 + n y 3 tiene orden 4 por lo que estamos hecho.
Ha habido mucha discusión en esta pregunta acerca de si ciertas pruebas contienen un oculto de inducción, por lo que esta respuesta formaliza lo que significa para una prueba de uso de la inducción, y explica que de las respuestas posibles del uso de la inducción con respecto a esta formalización.
Los números naturales son definidos por los axiomas de Peano, que puede ser declaró sucintamente como sigue:
Los números naturales $\mathbb{N}$ form un discretamente ordenó semiring.
Si $S\subconjunto \mathbb{N}$ tiene las propiedades que (yo) $0\in S$ y (ii) $(\forall n)(n\S \Rightarrow n+1\in S)$, entonces $S=\mathbb{N}$.
En axioma 1, un semiring es similar a un anillo, excepto que los elementos no tienen necesidad de inversos aditivos, y diciendo que es "discretamente ordenó" significa que hay un orden lineal en $\mathbb{N}$ que satisface ciertos axiomas. Ver aquí para una lista completa de los axiomas contenida en el axioma 1.
Axioma 2 es el axioma de inducción. Los axiomas 1 y 2, así como definir la Aritmética de Peano (PA), mientras que el axioma 1 solo define una teoría similar a la de los números naturales en el que la inducción no necesariamente. Esta teoría es a menudo denotado $\mathrm{PA}^-$.
Por lo que si algo puede ser probados", sin la inducción" es, esencialmente, preguntando si podemos probar la declaración en un modelo para $\mathrm{PA}^-$, es decir, preguntando si podemos probar la declaración por cualquier discretamente ordenó semiring.
Esto presenta un problema, porque no está claro exactamente lo que la "serie de Fibonacci" se refieren a un arbitrario discretamente ordenó semiring. He aquí una posible definición:
Definición. Vamos a $N$ ser un discretamente ordenó semiring. Una función de Fibonacci en $N$ es una función $f\colon N\N$ satisfacer las siguientes condiciones:
- $f(0) = 0$.
- $f(1) = 1$.
- $f(n+2) = f(n+1) + f(n)$ para todo $n\in$N.
Aquí $0$ denota la identidad aditiva de $N$, y $1$ denota la identidad multiplicativa.
Ahora, es posible demostrar el uso de la inducción de que existe una única función de Fibonacci en $\mathbb{N}$ (es decir, la habitual secuencia de Fibonacci), pero esto no es posible demostrar de manera arbitraria discretamente ordenó semiring $N$. De hecho, es posible demostrar (en ZFC) que una de Fibonacci función siempre existe, pero no va a ser únicos, a menos de $N$ es isomorfo a $\mathbb{N}$.
Sin embargo, esto no nos impide probar cosas acerca de arbitraria de Fibonacci funciones. He aquí una declaración y prueba de la OP del reclamo sin ningún tipo de inducción:
Teorema. Vamos a $N$ ser un discretamente ordenó semiring, y dejar que $f\colon N \N$ ser una función de Fibonacci. Entonces para todo $n\in$ N, existe un $k\in$ N, de modo que $$ f(n+20) = f(n) + 5k, $$ donde $5$ denota $1+1+1+1+1$ y $20$ denota $5+5+5+5$.
Prueba: vamos a seguir mathlove hermosa respuesta. Antes de la prueba inicia, tenga en cuenta que $$ N debe contener un canónica copia de $\mathbb{N}$, es decir, la subsemiring generada por $1$. Para mayor comodidad, vamos a suponer que $\mathbb{N}\subconjunto de N$, lo que nos permite utilizar constantes como $5$ sin explicar que $5$ significa $1+1+1+1+1$.
Observe primero que $$\begin{align}f(n+5) y= f(n+4)+f(n+3)\\&= f(n+3)+f(n+2)+f(n+2)+f(n+1)\\&= f(n+2)+f(n+1)+2(f(n+1)+f(n))+f(n+1)\\&= f(n+1)+f(n)+f(n+1)+2(f(n+1)+f(n))+f(n+1)\\&= 3f(n) + 5f(n+1)\end{align}$$ para todo $n\in$ N. Entonces $$\begin{align}f(n+20)&= 3f(n+15) + 5f(n+16)\\&= 3^2f(n+10) + 5\bigl(3f(n+11)+f(n+16)\bigr)\\&= 3^3 f(n+5) + 5\bigl(3^2 f(n+6)+3 f(n+11) + f(n+16)\bigr)f\\&= 3^4 f(n) + 5\bigl(3^3 f(n+1) + 3^2 f(n+6) + 3f(n+11) + f(n+16)\bigr),\end{align}$$ Pero $3^4 = 81 = 5(16) + 1$, y por lo tanto $$ f(n+20) = f(n) + 5\bigl(16f(n) + 3^3 f(n+1) + 3^2 f(n+6) + 3f(n+11) + f(n+16)\bigr). $$ Esto prueba la da el teorema de arbitrario discretamente ordenó semiring, con la no utilización de la inducción.
Así mathlove la respuesta es correcta, en el sentido de que el argumento legítimamente no uso de la inducción.
Sospecho que lulu respuesta hace uso de la inducción, aunque es difícil de decir, porque es más difícil ver cómo puede ser traducido al contexto de arbitrario discretamente ordenó semirings. También hay el problema de que la exponenciación no puede ser definida de forma única en una arbitraria ordeerd semiring. Tal vez lo que lulu ha demostrado es que no existe una función de Fibonacci con la propiedad deseada.
Como mathlove la respuesta, Elaqqad la respuesta que funciona bien en un arbitrario discretamente ordenó semiring, lo que significa que legítimamente no uso de la inducción.
Jack D'Aurizio la respuesta utiliza la fórmula de Binet, que, presumiblemente, no puede ser arbitrario discretamente ordenó semiring, aunque supongo que sería posible recuperar parte de la versión de la misma. Tendríamos que empezar por discutir si un arbitrario discretamente ordenó semiring puede ser incrustado en una especie de campo que contiene una raíz cuadrada de cinco, y en qué sentido podría ser posible definir la exponenciación en el campo con el exponente es un elemento de la semiring.
Klaus Draeger la respuesta de curso requiere de la inducción, pero sospecho que un argumento similar podría hacerse para el trabajo en general, simplemente mediante la sustitución de la inicial de $(1,0)$ por una arbitraria par $(a,b)$ y la reducción de modulo $5N$. (Como lo que yo puedo decir, que no tenemos ni idea de cómo es de grande $N/5N$ es en general, pero eso no significa que no podemos hacer los cálculos en el cociente. Tenga en cuenta que el uso de $N/5N$ hubiera simplificado la prueba anterior, a pesar de que habría aumentado la dificultad conceptual.)
Cristiano Blatter, la respuesta de los usos de la inducción para demostrar que $G_n=0$ para todo $n$. No veo una forma de evitar esto.
Otro enfoque posible. Deje que $\sigma$ a raíz del polinomio característico $x^2-x-1$. Tenemos:
$$ \sigma^2 = \sigma+1,\qquad \sigma^4 = \sigma^2+2\sigma+1 = 3\sigma+2, $$ $$ \sigma^8 = 9\sigma^2 + 12\sigma +4 = 21\sigma + 13,\qquad \sigma^{16} = 441\sigma^2 + 546\sigma + 169 = 987\sigma + 610,$$ por lo tanto: $$ \sigma^{20} = (3\sigma + 2)(987\sigma + 610) = 6765\sigma + 4181 = \sigma^0 + 55(123\sigma+76).$$ Si ahora multiplicamos ambos lados por $\sigma^n$ y el uso de la Binet la fórmula, podemos demostrar el más fuerte reclamo:
$$ \forall n\geq 0,\qquad \color{red}{55} \mid (F_{n+20}-F_n).$$
Prueba sin la inducción
En primer lugar tenemos : $$F_{n+20}=F_{n+19}+F_{n+18}=2F_{n+18}+F_{n+17}= 3F_{n+17}+2F_{n+16}$$
Si continúa la reducción de este $20$ veces se tienen: $$F_{n+20} = 10946 F_{n}+ 6765 F_{n-1} \etiqueta {*}$$
y desde aquí se puede ver que:
$$F_{n+20}\equiv F_n \mod 5 $$
Nota La fórmula $(*)$ puede ser calculada a $\mod 5$ que reduce los grandes números, pero va a tomar algún tiempo para terminar el cálculo, en realidad es la parte de una fórmula general que se puede demostrar por inducción : $$F_{p+q}=F_pF_{p+1}+F_{p-1}F_q $$ (tomar $p=n$ y $q=20$)
Respuesta a los comentarios acerca de la inducción
Si una secuencia es definida por inducción, a continuación, esto no significa que tenemos que usar la inducción para probar cada hecho acerca de esta secuencia. tomemos, por ejemplo, la secuencia de Fibonacci, no una necesidad de la inducción para demostrar que $F_2=1$ o que $F_3 = 2$? por supuesto que no . En realidad podemos formalizar la definición en dos afirmaciones: $$ \begin{align} (1) && F_0=0 , && F_1=1 \\ (2) && \forall n \in \mathbb{N} && F_{n+2}=F_{n+1}+F_n\end{align}$$
así que a partir de la primera afirmación que podemos probar directamente que (sin inducción) que $F_2=1,F_3=2,F_4=3,\cdots$, y a partir de la segunda afirmación podemos probar directamente que $\forall n \in \mathbb{N}\ \ \ F_{n+3}=F_{n+1}+2F_{n}$ y $$(3)\ \ \ \ \ \ \forall n\in \mathbb{N}\ \ \ \ F_{n+20}\equiv F_n \mod 20$$
Si queremos ser más precisos, diremos que podemos probar sin la inducción que "cada secuencia de $(F_n)_{n\in \mathbb{N}}$ verificación de $(2)$ debe verificar también $(3)$", y más formalmente: $$\forall (F_n)\in \mathbb{N}^{\mathbb{N}} \ \ \ \ \ big(\left(\forall n \in \mathbb{N} F_{n+2}=F_{n+1}+F_n\right)\implica\left(\forall n\in \mathbb{N} F_{n+20}\equiv F_n \mod 20\right)\big) $$
(y aquí no podemos ahora, si $F_n$ se define de forma única para demostrar que debemos utilizar la inducción)
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
