Prueba $\forall n \in \mathbb {N}$ , $6\vert (n^3-n)$ . (inducción fuerte)

Question

Una idea bastante directa para ser probada aquí, pero tratando de captar los fundamentos de lo que uno consideraría "inducción fuerte". Por favor, vea mi prueba a continuación, mis preguntas son: ¿es una prueba válida? ¿Es estilísticamente apropiado para una prueba por inducción fuerte?

EDIT: Lo siento porque no estaba claro en mi pregunta original, pero este post era más bien para ayudar a comprender los fundamentos de la Inducción Fuerte. Aunque gracias por señalar el método simplista de darse cuenta de que $(n^3-n)$ es simplemente el producto de tres enteros consecutivos y, por tanto, es divisible por un factor de $2$ y $3$ .

P: Demuestre que $\forall n \in \mathbb {N}$ , $6\vert (n^3-n)$ .

$Proof.$ Lo demostraremos por inducción matemática.

Caso base. Dejemos que $n=1$ y observar que $6\vert 0$ es cierto. Sea $n=2$ y observar que $6\vert 6$ es cierto. Por último, dejemos que $n=3$ y observar que $6\vert 24$ es cierto. Así, para $n\in\mathbb{N}$ donde $1\le n \le 3$ nuestra proposición se mantiene.

Paso inductivo. Supongamos que nuestra proposición es verdadera para $n=j$ donde $1\le j \le k$ y $k \ge 3$ . Desde $6\vert (k^3-k)$ sabemos $k^3-k=6l$ para algunos $l\in\mathbb{Z}$ .

Entonces

$$\begin{align}(k-2)^3-(k-2)&= k^3-6k^2+12k-8-k+2\\ &=(k^3-k)-6k^2+12k-6\\ &=6l-6k^2+12k-6\\ &=6(l-k^2+2k-1). \end{align}$$

Así, $\exists m\in\mathbb{Z},(k-2)^3-(k-2)=6m\Rightarrow 6\vert (k-2)^3-(k-2)$ . Se deduce por inducción matemática que $\forall n \in \mathbb {N}$ , $6\vert (n^3-n)$ . $\Box$

Answer 1

Prueba por inducción.

---

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

$1^3-1=0$

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

$n^3-n=6k$

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

$(n+1)^3-(n+1)=$

$n^3+3n^2+2n=$

$n^3+3n^2+3n-n=$

$\color\red{n^3-n}+3n^2+3n=$

$\color\red{6k}+3n^2+3n=$

$3(2k+n^2+n)=$

$3(2k+\color\green{n(n+1)})=$

$3(2k+\color\green{2m})=$

$3(2(k+m))=$

$6(k+m)$

---

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

Podemos sustituir $n(n+1)$ con $2m$ ya que, o bien $n$ es par o $n+1$ está en paz.

Answer 2

No estoy seguro de entender su paso inductivo. Dices que para todos $j$ tal que $1\leq j\leq k, 6|j^3-j$ y $k\geq 3$ . A continuación, debe demostrar que esta propiedad se mantiene para $k+1$ Es decir, $6|(k+1)^3+k+1$ . En cambio, parece que me muestra que $6|(k-2)^3-(k-2)$ .

En cambio, considere que $(k+1)^3-(k+1)=k^3+3k^2+2k$ y $(k-1)^3-(k-1)=k^3-3k^2+2k$ . Compara los dos.

Ten en cuenta que, aunque no es la inducción a la que estás acostumbrado (a veces llamada inducción débil o primer principio de inducción), esta inducción "fuerte" no es mucho más fuerte. La prueba sólo necesita el caso de que $k-1$ tiene la propiedad deseada para demostrar que $k+1$ también tiene la propiedad. La idea de la inducción fuerte es que se utiliza el hecho de que todos $j$ de $1$ a $k$ utilizar la propiedad deseada.

Un buen ejemplo sería la demostración del teorema fundamental de la aritmética; demostrar que todo número mayor que $1$ tiene una factorización prima, primero decimos que $2$ es primo (el caso base). Ahora dejemos que $k>2$ y decir que para todos $j$ tal que $2\leq j\leq k$ , $j$ tiene una factorización prima. Si $k+1$ es primo, es su propia factorización primaria. Si no, tiene un factor primo menor que él, digamos $p$ . Entonces $\frac{k+1}{p}$ tiene una factorización prima por la hipótesis de inducción fuerte, por lo que $k+1$ también lo hace. En este caso, toda la suposición para todos los $j$ es necesario, porque no se sabe exactamente qué $\frac{k+1}{p}$ es, sólo que es menos que $k+1$ .

Answer 3

Una forma de presentar esto como una prueba de inducción fuerte sería utilizar la estructura polinómica de $n^3-n$ para escribir la secuencia como la solución de una relación de recurrencia. Pensando en los operadores delta / derivados discretos (por ejemplo $\nabla f(n)=f(n)-f(n-1)$ o $\Delta f(n)=f(n+1)-f(n))$ y el hecho de que reducen el grado de los polinomios en uno, podemos ver que al definir

$$a_n=n^3-n$$

entonces con un poco de trabajo, vemos que

$$\Delta ^3a_n \equiv 6\implies a_{n+3}-3a_{n+2}+3a_{n+1}-a_{n}=6 \,\forall n$$

Así, podemos escribir $n^3-n$ como la única solución de la ecuación de recurrencia:

$$a_{n+3}=3a_{n+2}-3a_{n+1}+a_n+6$$

$$a_0=a_1=0,a_2=6$$

Observando rápidamente que $a_n$ es un múltiplo de $6$ para $n=0,1,2$ suponemos que esto es cierto para todos los $n<N$ y tratar de probar su verdad cuando $n=N$ (esto es la inducción).

Ahora, $a_{N}=3a_{N-1}-3a_{N-2}+a_{N-3}+6$ y como nuestra hipótesis de inducción dice que $a_{N-1},a_{N-2},a_{N-3}$ son todos múltiplos de $6$ es sencillo observar que $a_N$ debe ser también un múltiplo de $6$ .

Editar : En realidad, también se puede ir un poco más allá: $\Delta ^4 a_n \equiv 0$ y la primera $4$ se puede comprobar que los términos son múltiplos de $6$ . El mismo argumento con inducción fuerte muestra que todos los términos serán múltiplos de $6$ . Básicamente aquí, nos basamos en la recursión $a_{n+4}=4a_{n+3}-6a_{n+2}+4a_{n+1}-a_n$ .

Answer 4

Si no lo ves directamente como 2 respuestas aquí. Siempre puedes probar con todos los números. Me refiero a considerar n=6k, n=6k+1,...,n=6k+5. Déjeme darle un ejemplo

$(6k+5)^3-(6k+5)=216k^3+540k^2+450k-6k+120$ que es divisible por 6.