Demostrando que $7^n(3n+1)-1$ es divisible por 9

Question

Estoy tratando de probar el resultado anterior para todos $n\geq1$ pero después de sustituir en la hipótesis inductiva, termino con un resultado que no es obviamente divisible por 9.

Normalmente, con estos problemas de inducción de la divisibilidad, se deshace muy bien y podemos factorizar fácilmente, digamos, un 9 si la pregunta nos exigía demostrar que la expresión es divisible por 9. Sin embargo, en este caso, no me sale tal cosa.

Mi trabajo hasta el momento a continuación:

Hipótesis inductiva: $7^k(3k+1)-1=9N$ donde $N\in\mathbb{N}$

Paso inductivo:

$7^{k+1}(3k+4)-1 \\ =7\times 7^k(3k+1+3)-1 \\ =7\times \left [ 7^k(3k+1)+3\times 7^k \right ] -1 \\ = 7 \times \left [ 9N+1 + 3 \times 7^k \right ] -1 \\ = 63N+21\times 7^k+6 \\ = 3 \left [ 21N+7^{k+1}+2 \right ]$

Así que ahora tengo que demostrar de alguna manera que $21N+7^{k+1}+2$ es divisible por 3, pero no sé muy bien cómo proceder a partir de aquí...

Answer 1

${\rm mod}\ 9\!:\,\ \overbrace{7^n (1\!+\!3n) \equiv 7^n (1\!+\!3)^n}^{\rm\large Binomial\ Theorem}\! \equiv 28^n\equiv 1^n\equiv 1 $

---

Nota: $ $ Sólo utilizamos el primer $2$ en la expansión del binomio, y este caso especial tiene una prueba inductiva fácil cuyo paso inductivo consiste en multiplicar por $\,1+a\pmod{\!a^2},\,$ a saber:

$\!\begin{align}{\rm mod}\,\ \color{#c00}{a^2}\!:\,\ (1+ a)^n\, \ \ \equiv&\,\ \ 1 + na\qquad\qquad\,\ \ {\rm i.e.}\ \ P(n)\\[1pt] \Rightarrow\ \ (1+a)^{\color{}{n+1}}\! \equiv &\ (1+na)(1 + a)\quad\, {\rm by}\ \ 1+a \ \ \rm times\ prior\\ \equiv &\,\ \ 1+ na+a+n\color{#c00}{a^2}\\ \equiv &\,\ \ 1\!+\! (n\!+\!1)a\qquad\ \ \ {\rm i.e.}\ \ P(\color{}{n\!+\!1})\\[2pt] \end{align}$

Podríamos sustituir esta prueba en línea por la anterior (por $\,a=3)\,$ para obtener un explícito prueba por inducción en $n\,$ (independiente del Teorema del Binomio) pero al hacerlo se ofuscaría la estructura aritmética subyacente, es decir, deberíamos llamar al Teorema del Binomio por su nombre (frente a la llamada por valor = inline) para resaltar la estructura aritmética clave. La prueba sigue siendo inductiva, pero la inducción se ha encapsulado en un Teorema (ubicuo), con la ventaja de que podemos reutilizarlo fácilmente más adelante.

Ver aquí para un ejemplo análogo utilizando la primera tres términos del Teorema del Binomio.

Answer 2

Si $f(n)=7^n(3n+1)-1,$

$\displaystyle af(m)-f(m+1)=\cdots =1-a+7^m[3m(a-7)+a-28]$

$\displaystyle a=1\implies f(m)-f(m+1)=-7^m(18m+27)\equiv0\pmod9$

Así que, $9|f(m+1)\iff9|f(m)$

Ahora establece el caso base, es decir, $n=1$

Alternativamente, sin utilizar la inducción, $\displaystyle7^n=(1+6)^n\equiv1+6n\pmod9$

$\displaystyle\implies7^n(3n+1)\equiv(1+6n)(3n+1)\equiv1\pmod9$

Answer 3

Este es el paso inductivo. Supongamos que la afirmación es cierta para $n=k$ . Entonces sabemos que $$9\mid 7^k(3k+1)-1.$$ Consideremos el caso en el que $n=k+1$ . En este caso, la expresión es $$7^{k+1}(3(k+1)+1)-1.$$ Ahora, simplifiquemos esta expresión a $$7[7^k(3k+1)+7^k\cdot 3]-1.$$ Observamos que $7^k(3k+1)$ aparece en esta expresión, que es casi la hipótesis inductiva. Sumando y restando 1, obtenemos $$7[7^k(3k+1)-1+1+7^k\cdot 3]-1.$$ La expresión $7^k(3k+1)-1$ es divisible por 9 por la hipótesis inductiva, por lo que se puede ignorar. Esto deja que nos gustaría tener $$7^{k+1}\cdot 3+6$$ siendo divisible por $9$ .

Para demostrar esto, se puede hacer otra inducción: $7^n\cdot 3+6$ es divisible por $9$ para todos $n\geq 1$ . Cuando $n=1$ , entonces esto se expande a $27$ que es divisible por $9$ .

Para el caso inductivo, supongamos que para $n=k$ , $$9\mid 7^k\cdot 3+6$$ y considerar $n=k+1$ . En este caso, tiene $$7^{k+1}\cdot 3+6=7[7^k\cdot 3]+6.$$ Al notar que $7^k\cdot 3$ es casi la hipótesis inductiva, esto se puede simplificar a $$7[7^k\cdot 3+6-6]+6.$$ El $7^k\cdot 3+6$ es divisible por $9$ por la hipótesis inductiva, y esto deja $7\cdot 6-6=36$ que es divisible por $9$ .

Answer 4

No hace falta ninguna inducción para demostrarlo: basta con la simple aritmética modular. La afirmación es equivalente a $ 7^n(3n+1)\equiv 1\mod 9$ .

Primera nota $7$ tiene orden multiplicativo $3$ modulo $9$ desde $7^3\equiv 1 \mod 9$ .

Siguiente $n \equiv 0,\ 1$ o $-1 \mod 3$ .

• Si $n\equiv 0 \mod 3$ : $\quad 7^n(3n+1)\equiv 1\cdot (0+1)=1 \mod 9$ .
• Si $n\equiv 1 \mod 3$ : $\quad 7^n(3n+1)\equiv 7\cdot (3+1)=28\equiv 1 \mod 9$ .
• Si $n\equiv -1 \mod 3$ : $\quad 7^n(3n+1)\equiv 4\cdot (-3+1)=-8\equiv 1 \mod 9$ .

Answer 5

Primero, demuestre que esto es cierto para $n=1$ :

$7^1\cdot(3\cdot1+1)-1=9\cdot3$

En segundo lugar, supongamos que esto es cierto para $n$ :

$7^n\cdot(3n+1)-1=9k$

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

$7^{n+1}\cdot(3(n+1)+1)-1=$

$7^{n+1}\cdot(3n+3+1)-1=$

$7^{n+1}\cdot(3n+1+3)-1=$

$7^{n+1}\cdot(3n+1)+7^{n+1}\cdot(3)-1=$

$7\cdot\color{red}{7^n\cdot(3n+1)}+3\cdot7^{n+1}-1=$

$7\cdot(\color{red}{9k+1})+3\cdot7^{n+1}-1=$

$63k+7+3\cdot7^{n+1}-1=$

$63k+3\cdot7^{n+1}+6=$

$\color{blue}{3(21k+7^{n+1}+2)}$

Ahora:

• $7\equiv1\pmod3\implies$
• $\forall{m}\in\mathbb{N}:7^m\equiv1\pmod3\implies$
• $7^{n+1}\equiv1\pmod3\implies$
• $7^{n+1}+2\equiv3\pmod3\implies$
• $7^{n+1}+2\equiv0\pmod3\implies$
• $3|7^{n+1}+2\implies$
• $\exists{p}\in\mathbb{N}:7^{n+1}+2=3p\implies$
• $3(21k+7^{n+1}+2)=3(21k+3p)=3(3(7k+p))\color{blue}{=9(7k+p)}$

---

Tenga en cuenta que el supuesto sólo se utiliza en la parte marcada en rojo.