¿Cómo puedo demostrar por inducción que $9^k - 5^k$ es divisible por 4?

Question

Recientemente tenía esto en una prueba de matemáticas discretas, que lamentablemente creo que no he logrado. Pero la pregunta:

Demostrar que $9^k - 5^k$ es divisible por $4$.

Utilizando el enfoque único que aprendí en la clase, sustituye $n = k$ e intentó probar $k+1$ como esta:

$$9^{k+1} - 5^{k+1},$$

que sólo factores $9 \cdot 9^k - 5 \cdot 5^k$.

Pero yo no puedo factor $9^k - 5^k$, por lo que estoy totalmente atrapado.

Answer 1

${\color{White}{\text{Proof without words.}}}$

Answer 2

$$\begin{align} 9\cdot 9^k - 5\cdot 5^k & = (4 + 5)\cdot 9^k - 5\cdot 5^k \\ \\ & = 4\cdot 9^k + 5 \cdot 9^k - 5\cdot 5^k \\ \\ & = 4\cdot 9^k + 5(9^k - 5^k)\\ \\ & \quad \text{ use inductive hypothesis}\quad\cdots\end{align}$$

Answer 3

$9^{k+1}-5^{k+1}=(8+1)9^k-(4+1)5^k=9^k-5^k+4(2\cdot 9^k-5^k)$ El secreto a las pruebas de inducción es generalmente encontrar una manera de relacionarse con el caso de $k+1$ $k$ caso.

Alternativamente, sólo tenga en cuenta $9\equiv 1 \pmod 4, 5 \equiv 1 \pmod 4$, que $9^k-5^k \equiv 1^k-1^k \pmod 4$

Answer 4

Tenga en cuenta que la inducción no es realmente necesaria: en su lugar puede utilizar la identidad

$$x^n-y^n=(x-y)\sum_{k=0}^{n-1}x^ky^{n-1-k}\;.$$

En este caso se convierte en

$$9^n-5^n=4\sum_{k=0}^{n-1}x^ky^{n-1-k}\;,$$

y puesto que la suma claramente da un número entero, tenemos $4\mid 9^n-5^n$. La identidad es un estándar, pero también no es difícil de demostrar:

$$\begin{align*} (x-y)\sum_{k=0}^{n-1}x^ky^{n-1-k}&=x\sum_{k=0}^{n-1}x^ky^{n-1-k}-y\sum_{k=0}^{n-1}x^ky^{n-1-k}\\\\ &=\sum_{k=0}^{n-1}x^{k+1}y^{n-1-k}-\sum_{k=0}^{n-1}x^ky^{n-k}\\\\ &=\sum_{k=1}^nx^ky^{n-k}-\sum_{k=0}^{n-1}x^ky^{n-k}\\\\ &=x^ny^0+\sum_{k=1}^{n-1}x^ky^{n-k}-\sum_{k=1}^{n-1}x^ky^{n-k}-x^0y^n\\\\ &=x^n-y^n\;. \end{align*} $$

Answer 5

Suena como que usted entiende la idea básica, pero estás teniendo problemas con el "truco" en el paso inductivo. Esto es común para las pruebas por inducción matemática, y obtendrá mejor en él con más experiencia.

Como usted dijo, usted está asumiendo que $ 9^k-5^k $ es divisible por cuatro, y que quieren demostrar que $ 9^{k+1}-5^{k+1} $ es divisible por cuatro. Se dio cuenta de que se puede escribir de la última expresión como $9\cdot 9^k-5\cdot 5^k$, y usted dijo que usted está teniendo problemas con la aplicación de su asunción. ¿Qué sucede si usted agregue $9\cdot 5^k-9\cdot 5^k$ a su expresión? Esto es sólo cero, por lo que no está cambiando nada, pero usted puede escribir $$ 9^{k+1}-5^{k+1} =9\cdot 9^k-5\cdot 5^k+9\cdot 5^k-9\cdot 5^k =9\cdot (9^k-5^k)+(9-5)\cdot 5^k. $$ Por supuesto, el primer término, $9\cdot (9^k-5^k)$, es divisible por cuatro, y a través de la observación, el segundo término, $(9-5)\cdot 5^k$, es divisible por cuatro, por lo que la suma de los dos términos y, por tanto, $9^{k+1}-5^{k+1}$ son divisibles por cuatro. Esto es lo que quería mostrar.

Usted puede agregar siempre cero (o multiplicar por uno), y por la escritura de cero (o uno) de manera particular, a veces se puede hacer un argumento más fácil de probar. También, ya que su prueba es por inducción matemática, usted necesita demostrar que $9^n-5^n$ es divisible por cuatro, por ejemplo, $n=0$ o $n=1$. Puede que ya lo han hecho y no se le preguntó al respecto en su pregunta, pero es que vale la pena mencionar.