Demostrar por inducción que $11$ divide $10^{2n}-1$ para todos los números naturales.

Question

$$10^{2(k+1)}-1 = 10^{2k+2}-1=10^{2k}\cdot10^{2}-1$$

Siento que hay algo en esa última parte, que tiene que hacer el trabajo, pero no puedo comprenderlo. Me estoy perdiendo algo que es obvio? Se me va completamente en la dirección equivocada? Cualquier ayuda se agradece.

Answer 1

En un comentario, observación de que usted no tiene idea de cómo Andre pensamiento de la prueba inductiva. A continuación vamos a mostrar que no es un truco de magia, sino que es un caso especial de un simple método general que trabaja para las inducciones de este tipo. A continuación se muestran muy explícitamente cómo el inductivo pasos en las pruebas por Andre y oujdid ambos son , precisamente, los casos especiales de las pruebas de la Congruencia de los Productos de la Regla. Usted no necesita estar familiarizado con congruencias para entender esto, ya que también escribe en equivalente de divisibilidad forma. Recordemos que $\rm\ n\mid k\,$ $\rm\,n\,$ divide $\rm\,k.\,$

${\bf Claim}\rm\qquad 10^2\!\equiv 1, \, 10^{2k}\!\equiv 1\ \, \Rightarrow\,\ 10^{2(k+1)}\!\equiv 1\ \, \pmod{\!11} $

${\bf Lemma}\rm\qquad\! A\equiv a,\ \, B\equiv b\quad \Rightarrow\quad\,\ AB\equiv ab\ \ \pmod{\!n}\ \ $ [$\rm\color{#c00}C$ongruence $\rm\color{#c00}P$roducto $\rm\color{#c00}R$ule]

$\rm\quad\ \ i.e.\quad\! n\mid\ A-a,\ \ B\,-\,b\ \Rightarrow\,\ n\mid \,AB\,-\,ab\qquad\qquad\ \ \ $ [$\rm\color{#c00}{CPR}\,$ en la divisibilidad de formulario]

${\bf Proof}\quad \rm n\mid\ A-a,\ \ B\,-\,b\,\Rightarrow\,\ n\mid \ A\ (\ B\,-\,b)+\,(\ A-a)b\, =\ \,A\, B\,-\,a\,b$

$\rm\quad\ e.g.\,\ 11\mid 10^2\!-\!1,10^{2k}\!-\!1\,\Rightarrow 11\mid\! 10^2(10^{2k}\!-\!1)+(10^2\!-\!1)1\,= 10^{2(k+1)}\!-1\ \ $ [André]

${\bf Proof}\quad \rm n\mid\ A-a,\ \ B\,-\,b\,\Rightarrow\,\ n\mid (\, A-a)\,\ B\ \ +a\ (\ B-b)\, =\ \,A\, B\,-\,a\,b$

$\rm\quad\ e.g.\,\ 11\mid 10^2\!-\!1,10^{2k}\!-\!1\,\Rightarrow 11\mid(10^2\!-\!1)10^{2k}\!+\! 1(10^{2k}\!\!-\!1) = 10^{2(k+1)}\!-1\ \ $ [oujdid]

Así que el inductivo pasos de André y oujdid - que parecen haber sido sacados de un sombrero como por arte de magia, en realidad tienen nada pero los casos especiales de las pruebas de la Congruencia de los Productos de la Regla. Una vez que sabemos de esta regla, no hay necesidad de repetir toda la prueba cada vez que se emplean. Más bien, simplemente podemos invocar la regla como un Lexema (en forma de divisibilidad si congruencias aún no son conocidas). A continuación, el paso inductivo ha vivos aritmética de la estructura, siendo simplemente el cálculo de un producto $\, 10^2\!\cdot 10^{2k}\equiv 10^{2(k+1)}.\,$ ya No es la innata aritmética de la estructura de la inducción ofuscado por los detalles de la prueba pf el Producto de la Regla ya que la prueba ha sido encapsulada en un Lema para la conveniente reutilizar.

De la misma manera, congruencias a menudo permiten impartir intuitiva aritmética estructura en inductiva pruebas - lo que nos permite reutilizar nuestro perfeccionado grado de la escuela las habilidades de manipulación aritmética de las ecuaciones (frente a los más complejos de la divisibilidad de las relaciones). A menudo la introducción de congruencia lenguaje servirá para simplificar en gran medida de la inducción, por ejemplo, la reducción de la misma a un trivial de inducción como $\, 1^n\equiv 1,\,$ o $\,(-1)^{2n}\equiv 1.\,$ El último es la esencia de la cuestión anterior, el cobre.sombrero de respuesta.

Answer 2

Uno realmente no necesita de inducción para esto:

$$\begin{align*} 10^{2n}-1&=\underbrace{999999\ldots999999}_{2n\text{ nines}}\\ &=\underbrace{99\,99\,99\,\ldots\,99\,99\,99}_{n\text{ copies of }99}\\ &=11\cdot\underbrace{09\,09\,09\,\ldots\,09\,09\,09}_{n\text{ copies of }09}\\ &=11\cdot 9\underbrace{090909\ldots090909}_{n-1\text{ copies of }09}\;. \end{align*}\etiqueta{1}$$

Sin embargo, si usted está obligado a utilizar la inducción puede utilizar el cálculo de arriba a trabajar de lo que debe suceder en la inducción de paso. Es bastante claro que de $(1)$ que $10^{2n+2}-1$ va a ser $11$ multiplicado por el número formado por un $9$, seguido por $n$ copias de $09$:

$$\begin{align*} 10^{2n+2}-1&=11\cdot 9\underbrace{090909\ldots090909}_{n\text{ copies of }09}\\ &=11\cdot 9\underbrace{090909\ldots090909}_{n-1\text{ copies of }09}09\\ &=11\left(100\cdot9\underbrace{090909\ldots090909}_{n-1\text{ copies of }09}+9\right)\\ &=100\cdot11\cdot9\underbrace{090909\ldots090909}_{n-1\text{ copies of }09}+11\cdot9\\ &=100\left(10^{2n}-1\right)+11\cdot 9\;, \end{align*}$$

así que si $10^{2n}-1$ es un múltiplo de a $11$, por lo que es $10^{2n+2}$.

Ahora usted puede limpiar la inducción paso por la eliminación de todas las explícito decimal representaciones y va directamente (o casi) de$10^{2n+2}$$100\left(10^{2n}-1\right)+11\cdot9$; el dígito de seguimiento puede entonces ser considerado simplemente como una manera de averiguar lo que está pasando.

Answer 3

Sólo en caso de que, una solución sin la inducción (o al menos alguna de inducción es enterrado en algún lugar):

Tenemos $[10]_{11} = [-1]_{11}$, y por lo $[10^{2n}]_{11} = [(-1)^{2n}]_{11} = [1]_{11}$

A continuación,$[10^{2n}-1]_{11} = 0$$11 \mid 10^{2n}-1$.

Notación: $[a]_b = a+b \mathbb{Z}$.

Answer 4

En primer lugar, demostrar que esto es cierto para $n=1$:

$10^{2}-1=11\cdot9$

Segundo, se supone que esto es cierto para $n$:

$10^{2n}-1=11k$

Tercero, demostrar que esto es cierto para $n+1$:

$10^{2(n+1)}-1=$

$10^{2n+2}-1=$

$100(10^{2n})-1=$

$100(\color{red}{10^{2n}-1})+99=$

$100(\color{red}{11k})+99=$

$11(100k+9)=$

---

Por favor, tenga en cuenta que la hipótesis se utiliza sólo en la parte marcada con rojo.