Demostrar divisibilidad mediante inducción.

Question

Pregunta:

Deje que$a$ sea un número entero diferente de$1$. Demostrar por inducción, que para cualquier$n \in\Bbb N$,$ a^n -1$ es divisible por$a-1$.

Mi intento:

El caso base es trivial.

IH: Supongamos que$ a^k -1$ es divisible por$a-1$,$k \in N$

Entonces,

$$ a^{k+1} -1 = a\cdot a^k -1 + a^k -1 - a^k + 1 = a\cdot a^k - a^k + a^k -1 = (a^k)(a-1) + (a^k -1)$$which is divisible by $ a-1 $.

Por lo tanto, probado por inducción.

¿Es esta la manera correcta de probarlo usando la inducción? ¿Hay alguna forma más eficiente de demostrarlo usando inducción?

Answer 1

Sugerencia $\ $ El paso inductivo de la siguiente manera por telescopy. $ $ Deje $f(k)= a^k-1$

A continuación, $\,\color{#0a0}{f(k\!+\!1)\!-\!f(k)} = a^{k+1}-a^k = (a\!-\!1)a^k$ es divisible por $\,a\!-\!1$

así que si $\,\color{#c00}{f(k)}$ es divisible por $\,a\!-\!1\,$, entonces también lo es $\,f(k\!+\!1) = \color{#0a0}{f(k+1)\!-\!f(k)} + \color{#c00}{f(k)}$

Comentario $ $ Sumando lo anterior hace que el telescópica cancelación explícito

$$\begin{align}a^{k+1}-1 =\, &\,\ \ \color{#c00}{a^{k+1}\!-a^k}+\color{#0a0}{a^k\!-a^{k-1}} + \cdots+ a^1\!-a^0\\[.3em] =\, &\,(a-1)\, (\color{#c00}{a^k} + \color{#0a0}{a^{k-1}}+\cdots+1) \end{align}$$

o, escrito de manera más formal

$$ f(k\!+\!1)-f(0) = \sum_{i=0}^k (f(i\!+\!1)\!-\!f(i)) = \sum_{i=0}^ka^i(a\!-\!1)) = (a\!-\!1)\sum_{i=0}^k a^i = (a\!-\!1)(a^k +\cdots + a + 1)$$

La primera igualdad por encima, expresando $f(k\!+\!1)-f(0)$ como la suma de sus primeras diferencias, tiene un trivial (y obvio) prueba por inducción. Una vez que usted pruebe esta forma general de manera inductiva, se puede utilizar como un lema para inductiva de probar muchos de los casos especiales que son omnipresentes. Usted puede encontrar muchos ejemplos y mucho más debate telescópica de inducción en diferentes antes de puestos.

Answer 2

Deje que$a>1$ sea un número entero. Demuestre por inducción que para cualquier$n \in \mathbb{N}$,$ a^n -1$ es divisible por$a-1$.

$\textbf{Proof}.$ Caso base: deje$n=1$. Entonces está claro que$a-1|a-1$.

Hipótesis de inducción: suponga que$a-1|a^k-1$ para algún entero$k$. Considere$a^{k+1}-1$, que podría reescribirse como $$ \begin{align*} a^{k+1}-1 &= a\cdot a^k + a^k-a^k-1 \\ &= a^k(a-1)+ (a^k-1). \\ \end {align *} $$ Desde$a-1|a^k(a-1)$ y$a-1|a^k-1$ por la hipótesis de inducción,$a-1|a^{k+1}-1$.

Por lo tanto,$a-1|a^n-1$.