5 votos

Inducción completa de $10^n \equiv (-1)^n \pmod{11}$

Para probar el $10^n \equiv (-1)^n\pmod{11}$, $n\geq 0$, empecé la inducción.

La $$11|((-1)^n - 10^n) \Longrightarrow (-1)^n -10^n = k*11,\quad k \in \mathbb{Z}. $ $

$n = 0$: $$ (-1)^0 - (10)^0 = 0*11 $ $

#% $$-$n\Rightarrow n+1$-#-{align*} $$ pero no consigo el siguiente paso.

11voto

Lorin Hochstein Puntos 11816

De no configurar su inducción muy bien. Usted no debe comenzar con la igualdad desea establecer, a saber, que $(-1)^{n+1}-10^{n+1}$ es un múltiplo de a $11$. En su lugar, usted debe comenzar con la Hipótesis de Inducción, que es el $(-1)^n - 10^n$ es un múltiplo de a $11$.

Por lo tanto: el Inductivo Paso es mostrar que si $(-1)^n - 10^n$ es un múltiplo de a $11$, a continuación, $(-1)^{n+1} - 10^{n+1}$ es también un múltiplo de $11$.

Vamos a escribir nuestra Hipótesis de Inducción: se dice que $$\text{There exists an integer }k\text{ such that }(-1)^n - 10^n = 11k.$$

Lo que queremos demostrar es que: $$\text{there exists an integer }\ell\text{ such that }(-1)^{n+1}-10^{n+1}=11\ell.$$ (Tenga en cuenta que las múltiples pueden ser diferentes, por eso utilicé una letra diferente).

Así que ahora podemos tratar de manipular la expresión que queremos. Una posibilidad es utilizar la siguiente identidad: $$a^{n+1}-b^{n+1} = (a-b)(a^n + a^{n-1}b + a^{n-2}b^2 + \cdots + ab^{n-1}+b^n),$$ si usted ya sabe que esta identidad.

Así tenemos, con $a=-1$$b=10$, $$ (-1)^{n+1} - 10^{n+1} = \Bigl( (-1) - 10\Bigr)\Bigl( (-1)^n + (-1)^{n-1}(10) + \cdots + (-1)10^{n-1} + 10^n\Bigr).$$ Ahora observe que no es necesario usar la inducción de la hipótesis a la conclusión de que la $(-1)^{n+1}-10^{n+1}$ es un múltiplo de a $11$ (como puede ser visto en mac respuesta).

Si usted no sabe la identidad, entonces usted puede realizar algunas puramente manipulaciones algebraicas. E. g., $$\begin{align*} (-1)^{n+1} - 10^{n+1} &= -1\left( (-1)^n + 10^{n+1}\right)\\ &= -\left( (-1)^n -10^n + 10^n + 10^{n+1}\right)\\ &= -\left( \Bigl((-1)^n - 10^n\Bigr) + 10^n\Bigl(1 + 10\Bigr)\right)\\ &= -\left( 11k + 10^n(11)\right) &\quad&\text{(by the induction hypothesis)}\\ &= -\left( 11(k+10^n)\right)\\ &= 11\left( -(k+10^n)\right), \end{align*}$$ que le da ese $(-1)^{n+1} - 10^{n+1}$ es un múltiplo de a $11$, como se desee, a partir de la suposición de que $(-1)^n - 10^n$ es un múltiplo de a $11$.


Pero más fácil aún es el uso de la siguiente propiedad de congruencias:

La proposición. Deje $a,b,c,d,k$ ser números enteros. Si $$a\equiv b\pmod{k}\qquad\text{and}\qquad c\equiv d\pmod{k}$$ a continuación,$ac\equiv bd\pmod{k}$.

Prueba. Desde $a\equiv b\pmod{k}$,$k|a-b$, lo $k$ divide cualquier múltiplo de $a-b$; por ejemplo, $k|(a-b)c = ac-bc$. Desde $k$ divide $ac-bc$,$ac\equiv bc\pmod{k}$.

Desde $c\equiv d\pmod{k}$,$k|c-d$, lo $k|(c-d)b = cb-db$, por lo tanto $bc\equiv bd\pmod{k}$.

Desde $ac\equiv bc\pmod{k}$$bc\equiv bd\pmod{k}$,$ac\equiv bd\pmod{k}$. QED

Corolario. Si $a_1\equiv b_1\pmod{k}$, $a_2\equiv b_2\pmod{k},\ldots, a_n\equiv b_n\pmod{k}$, entonces $$a_1\cdots a_n\equiv b_1\cdots b_n\pmod{k}.$$

Prueba. Inducción en $n$. QED

(Aquí es donde usted desea utilizar la inducción, más que en el caso específico que usted está mirando).

Corolario. Si $a\equiv b\pmod{k}$, para todos los enteros positivos $n$, $a^n\equiv b^n\pmod{k}$.

Prueba. Aplicar el corolario anterior con $a_i=a$ $b_i=b$ todos los $i$. QED

5voto

Shabaz Puntos 403

Si desea utilizar la inducción, asume que$(-1)^n-10^n=11k$ Entonces quiere probar$(-1)^{(n+1)}-10^{(n+1)}=11m$. Asi que $(-1)^{(n+1)}-10^{(n+1)}=-1(-1)^n-10(10^n)=-1(11k+10^n)-10(10^n)=-11k-11(10^n)=11m$

3voto

PSU_Kardi Puntos 101

Desde 10 ≡ -1 (mod 11), puedes elevar ambos lados a la potencia de$n$.

3voto

David HAust Puntos 2696

A continuación se presentan algunas observaciones sobre inductivo pruebas de que son demasiado largos para los comentarios. El principal punto que me gustaría destacar es que cuando usted está aprendiendo cómo presentar pruebas rigurosas por inducción matemática es importante tener cuidado para evitar componer circular pruebas. Vamos a considerar un ejemplo específico. En otra respuesta aquí una prueba de que el resultado deseado, que $\rm\ 10^n\equiv (-1)^n\ (mod\ 11)\:,\:$ fue propuesto con base en los siguientes identidad, que es verdadera para todos los enteros $\rm\:a,b\:$ y todos los naturales de $\rm\:n\:$

$$\rm a^{n+1}-b^{n+1}\ =\ (a-b)\ (a^n + a^{n-1}b + a^{n-2}b^2 + \cdots + ab^{n-1}+b^n) $$

El tratado de resultado se sigue inmediatamente al que se especializa $\rm\: a = 10,\: b = -1\:$ en la anterior identidad.

Significa lo anterior constituye una prueba válida por la inducción de la buscó resultado? Probablemente su instructor de aceptar como válida la prueba en caso de que usted primero pruebe por inducción dijo identidad y, a continuación, derivado del tratado de resultado como corolario, por la especialización de la identidad como se ha indicado anteriormente. Sin embargo, si usted no tiene ya disponible una rigurosa prueba de que la identidad es cierto para todos los $\rm\:n\:$, entonces no sería correcto para invocar la identidad en su prueba, ya que, en efecto, se estaría suponiendo que la verdad más general resultado, que a su vez requiere de una rigurosa prueba por inducción. Aunque puede que haya aprendido de esta identidad en sus estudios previos, antes de aprender cómo dar riguroso inductivo pruebas, probablemente en ese momento no tenía a su disposición las herramientas para dar una rigurosa prueba. Tal vez usted puede incluso haber aprendido más general de los resultados, tales como el Teorema de Factor $\rm\ x-y\ |\ f(x)-f(y)\:$ $\rm\:\mathbb Z[x,y]\:$ para todos los polinomios $\rm\:f(x)\in\mathbb Z[x]\:.\:$ Pero esto también requiere de una rigurosa prueba inductiva, por ejemplo, a través de la inducción en $\rm\: deg\ f\:.\:$

Por lo tanto, si usted se propone abordar un ejercicio de inducción por "pasar el inductivo buck" a lo más general resultado, asegúrese de que usted ya ha dado un riguroso inductivo prueba de ese resultado. Desde el punto de tales ejercicios es proporcionar experiencia para ayudar a fortalecer su inductivo de la intuición, es esencial para la experiencia de la inducción - ya sea en forma específica o de forma general.

Una vez que haya adquirido cierta experiencia con inductivo pruebas es importante hacer una introspección de un bit en un meta-nivel abstracto a cabo diversos patrones comunes de inducción. Por ejemplo, muchos de mis posts aquí enfatizar el hecho de que muchos de los más comunes inductivo pruebas son simplemente casos especiales de telescopy. Al darse cuenta de esta estructura telescópica, a menudo se puede reducir la inducción a un muy trivial forma normalizada, por ejemplo, para el trivial de inducción que $\rm\: 1^n = 1\:.\:$ reducción de inductivo complejidad libera de nuestras facultades mentales, de manera que podamos concentrarnos en los aspectos más esenciales del problema.

-2voto

paul Puntos 416

Prueba directa:$10^n=(11-1)^n=11(\dots)+(-1)^n$

i-Ciencias.com

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.

Powered by:

X