¿Cuál es exactamente la diferencia entre la inducción débil y la inducción fuerte?

Question

Tengo problemas para ver la diferencia entre la inducción débil y la inducción fuerte.

---

Hay algunos ejemplos en los que podemos ver la diferencia, tales como alcanzar el $k^{th}$ escalón de una escalera y probar que todo entero $>1$ puede ser escrito como un producto de números primos:

Para demostrar que todo $n\ge2$ puede ser escrito como un producto de números primos, primero notamos que $2$ es primo. Ahora suponemos verdadero para todos los enteros $2 \le m. Si $n$ es primo, hemos terminado. Si $n$ no es primo, entonces es compuesto y por lo tanto $n=ab$, donde $a$ y $b$ son menores que $n$. Dado que $a$ y $b$ son menores que $n$, $ab$ puede ser escrito como un producto de números primos y por lo tanto $n$ puede ser escrito como un producto de números primos. QED

---

Sin embargo, parece ser algo parecido a la inducción débil, solo un poco dudoso. En la inducción débil, mostramos un caso base es verdadero, luego asumimos que es verdadero para todos los enteros $k-1$, (o $k$), luego intentamos mostrar que es verdadero para $k$, (o $k+1$), lo que implica verdad $\forall n \in \mathbb N$.

Cuando asumimos que es verdadero para todos los enteros $k$, ¿no es eso lo mismo que una hipótesis de inducción fuerte? Es decir, estamos asumiendo que es verdadero para todos los enteros hasta algún específico.

---

Como ejemplo demostrativo simple, ¿cómo mostraríamos $1+2+\cdots+n= {n(n+1) \over 2}$ usando inducción fuerte?

(Aprendido del libro Matemáticas Discretas de Kenneth Rosen)

Answer 1

Observaciones iniciales: Buena pregunta. Creo que merece una respuesta completa (aviso: va a ser una respuesta larga, pero espero que muy clara). En primer lugar, la mayoría de los estudiantes no entienden realmente por qué la inducción matemática es una técnica de demostración válida . Eso es parte del problema. En segundo lugar, la inducción débil y la inducción fuerte son en realidad lógicamente equivalentes; por tanto, diferenciar entre estas formas de inducción puede parecer un poco difícil al principio. Lo importante es entender cómo se enuncian la inducción débil y la fuerte y comprender claramente las diferencias entre ellas (no estoy de acuerdo con la respuesta anterior de que es "sólo una cuestión de semántica"; no lo es, y explicaré por qué). Gran parte de lo que voy a decir está adaptado del maravilloso libro de David Gunderson Manual de inducción matemática Pero he ampliado y retocado algunas cosas cuando lo he considerado oportuno. Dicho esto, espero que el resto de esta respuesta te resulte informativa.

---

Comentario de Gunderson sobre la inducción fuerte: Al intentar una prueba inductiva, en el paso inductivo a menudo sólo se necesita la verdad de $S(n)$ para demostrar $S(n+1)$ pero a veces se necesita un poco más de "potencia" (como en la prueba de que cualquier número entero positivo $n\geq 2$ es un producto de primos--exploraremos por qué se necesita más potencia en un momento), y a menudo esto se hace posible reforzando la hipótesis inductiva.

---

Comentario de Kenneth Rosen en Guía de estudio de Matemáticas discretas y sus aplicaciones : Comprender y construir pruebas por inducción matemática son tareas extremadamente difíciles para la mayoría de los estudiantes. No te desanimes, ni te rindas, porque, sin duda, esta técnica de demostración es la más importante que existe en matemáticas y en informática. Presta mucha atención a las convenciones que hay que observar al escribir una prueba por inducción. Como con todas las pruebas, recuerde que una prueba por inducción matemática es como un ensayo: debe tener un principio, un medio y un final; debe consistir en oraciones completas, ordenadas lógica y estéticamente; y debe convencer al lector. Asegúrese de que su paso base (también llamado "caso base") es correcto (que ha verificado la proposición en cuestión para el valor o valores más pequeños de $n$ ), y asegúrese de que su paso inductivo es correcto y completo (que ha derivado la proposición para $k+1$ asumiendo la hipótesis inductiva de que la proposición es verdadera para $k$ --o la hipótesis ligeramente fuerte de que es verdadera para todos los valores menores o iguales a $k$ Cuando se utiliza la inducción fuerte.

---

Declaración de inducción débil: Dejemos que $S(n)$ denota una declaración relativa a un número entero $n$ y que $k\in\mathbb{Z}$ se arreglen. Si

• (i) $S(k)$ se mantiene, y
• (ii) para cada $m\geq k, S(m)\to S(m+1)$ ,

entonces para cada $n\geq k$ La declaración $S(n)$ se mantiene.

---

Declaración de inducción fuerte: Dejemos que $S(n)$ denota una declaración relativa a un número entero $n$ . Si

• (i) $S(k)$ es verdadera y
• (ii) para cada $m\geq k, [S(k)\land S(k+1)\land\cdots\land S(m)]\to S(m+1)$ ,

entonces para cada $n\geq k$ La declaración $S(n)$ es cierto.

---

Prueba de la inducción fuerte a partir de la débil: Supongamos que para algunos $k$ La declaración $S(k)$ es verdadera y para cada $m\geq k, [S(k)\land S(k+1)\land\cdot\land S(m)]\to S(m+1)$ . Dejemos que $B$ sea el conjunto de todos los $n>m$ para lo cual $S(n)$ es falso. Si $B\neq\varnothing, B\subset\mathbb{N}$ y así por el buen orden, $B$ tiene un elemento mínimo, por ejemplo $\ell$ . Según la definición de $B$ para cada $k\leq t<\ell, S(t)$ es verdadera. La premisa de la hipótesis inductiva es verdadera, por lo que $S(\ell)$ es verdadera, contradiciendo que $\ell\in B$ . Por lo tanto, $B=\varnothing$ . $\blacksquare$

---

Prueba de la inducción débil a partir de la fuerte: Supongamos que la inducción fuerte se mantiene (en particular, para $k=1$ ). Es decir, supongamos que si $S(1)$ es verdadera y para cada $m\geq 1, [S(1)\land S(2)\land\cdots\land S(m)]\to S(m+1)$ , entonces para cada $n\geq 1, S(n)$ es cierto.

Obsérvese (mediante tablas de verdad, si se desea), que para $m+1$ declaraciones $p_i$ , $$ [p_1\to p_2]\land[p_2\to p_3]\land\cdots\land[p_m\to p_{m+1}]\Rightarrow[(p_1\land p_2\land\cdots\land p_m)\to p_{m+1}],\tag{$\dagger$} $$ es un resultado demostrable por inducción (véase el final de la respuesta para dicha demostración).

Supongamos que las hipótesis de la inducción débil son verdaderas, es decir, que $S(1)$ es verdadera, y que para un $t, S(t)\to S(t+1)$ . Mediante la aplicación repetida de estos supuestos recientes, $S(1)\to S(2), S(2)\to S(3),\ldots, S(m)\to S(m+1)$ cada una de ellas. Por la observación anterior, entonces $$ [S(1)\land S(2)\land\cdots\land S(m)]\to S(m+1). $$ Así, las hipótesis de la inducción fuerte son completas, por lo que se concluye que para cada $n\geq 1$ La declaración $S(n)$ es verdadera, la consecuencia deseada para completar la prueba de la inducción débil. $\blacksquare$

---

Demostrar cualquier número entero positivo $n\geq 2$ es un producto de primos utilizando la inducción fuerte: Dejemos que $S(n)$ sea la declaración " $n$ es un producto de primos".

Paso de base ( $n=2$ ): Desde $n=2$ es trivialmente un producto de primos (en realidad, un primo), $S(2)$ es cierto.

Paso inductivo: Arreglar algunos $m\geq 2$ y asumir que para cada $t$ Satisfaciendo a $2\leq t\leq m$ La declaración $S(t)$ es cierto. Lo que hay que demostrar es que $$ S(m+1) : m+1 \text{ is a product of primes}, $$ es cierto. Si $m+1$ es un primo, entonces $S(m+1)$ es cierto. Si $m+1$ no es primo, entonces existe $r$ y $s$ con $2\leq r\leq m$ y $2\leq s\leq m$ para que $m+1=rs$ . Desde $S(r)$ se supone que es verdadera, $r$ es un producto de primos [ nota: Este es donde es imperativo que usemos la inducción fuerte; usando la inducción débil, no podemos asumir $S(r)$ es verdadero]; de forma similar, por $S(s), s$ es un producto de primos. Por lo tanto, $m+1=rs$ es un producto de primos, por lo que $S(m+1)$ se mantiene. Por lo tanto, en cualquier caso, $S(m+1)$ se mantiene, completando el paso inductivo.

Por inducción matemática, para todo $n\geq 2$ La declaración $S(n)$ es cierto. $\blacksquare$

---

Prueba de $1+2+3+\cdots+n = \frac{n(n+1)}{2}$ por inducción fuerte: Usar la inducción fuerte aquí es completamente innecesario, ya que no la necesitas en absoluto, y sólo es probable que confunda a la gente en cuanto a por qué la estás usando. Se procederá igual que una prueba por inducción débil, pero la suposición de partida será diferente; no obstante, sólo para mostrar de qué estoy hablando, lo demostraré usando la inducción fuerte.

Dejemos que $S(n)$ denota la proposición $$ S(n) : 1+2+3+\cdots+n = \frac{n(n+1)}{2}. $$

Paso de base ( $n=1$ ): $S(1)$ es cierto porque $1=\frac{1(1+1)}{2}$ .

Paso inductivo: Arreglar algunos $k\geq 1$ y asumir que para cada $t$ Satisfaciendo a $1\leq t\leq k$ La declaración $S(t)$ es cierto. Lo que hay que demostrar es que $$ S(k+1) : 1+2+3+\cdots+k+(k+1)=\frac{(k+1)(k+2)}{2} $$ es lo siguiente. Empezando por el lado izquierdo de $S(k+1)$ , \begin {align} \text {LHS} &= 1+2+3+ \cdots +k+(k+1) \tag {por definición} \\ [1em] &= (1+2+3+ \cdots +k)+(k+1) \tag {términos del grupo} \\ [1em] &= \frac {k(k+1)}{2}+(k+1) \tag {por $S(k)$ } \\ [1em] &= (k+1) \left ( \frac {k}{2}+1 \right ) \tag {factor de salida $k+1$ } \\ [1em] &= (k+1) \left ( \frac {k+2}{2} \right ) \tag {denominador común} \\ [1em] &= \frac {(k+1)(k+2)}{2} \tag {expresión deseada} \\ [1em] &= \text {RHS}, \end {align} obtenemos el lado derecho de $S(k+1)$ .

Por inducción matemática, para todo $n\geq 1$ La declaración $S(n)$ es cierto. $\blacksquare$

$\color{red}{\text{Comment:}}$ ¿Ves cómo esto no es diferente de cómo funcionaría una prueba por inducción débil? La única diferencia es una suposición innecesaria hecha al principio de la prueba. Sin embargo, en tu prueba de números primos, la inducción fuerte es esencial; de lo contrario, no podemos suponer $S(r)$ o $S(s)$ que sea cierto. En este caso, cualquier suposición relativa a $t$ donde $1\leq t\leq k$ es realmente inútil porque no la utilizamos en ninguna parte de la prueba, mientras que sí utilizamos los supuestos $S(r)$ y $S(s)$ en la prueba del número primo, donde $1\leq t\leq m$ porque $r,s < m$ . ¿Tiene ahora sentido por qué era necesario utilizar la inducción fuerte en la prueba de los números primos?

---

Prueba de $(\dagger)$ por inducción: Para las declaraciones $p_1,\ldots,p_{m+1}$ tenemos que $$ [p_1\to p_2]\land[p_2\to p_3]\land\cdots\land[p_m\to p_{m+1}]\Rightarrow[(p_1\land p_2\land\cdots\land p_m)\to p_{m+1}]. $$

Prueba. Para cada $m\in\mathbb{Z^+}$ , dejemos que $S(m)$ sea la afirmación de que para $m+1$ declaraciones $p_i$ , $$ S(m) : [p_1\to p_2]\land[p_2\to p_3]\land\cdots\land[p_m\to p_{m+1}]\Rightarrow[(p_1\land p_2\land\cdots\land p_m)\to p_{m+1}]. $$ Paso básico: La declaración $S(1)$ dice $$ [p_1\to p_2]\Rightarrow [(p_1\land p_2)\to p_2], $$ que es verdadera (ya que el lado derecho es una tautología).

Paso inductivo: Fijar $k\geq 1$ y asumir que para cualquier declaración $q_1,\ldots,q_{k+1}$ , ambos $$ S(1) : [q_1\to q_2]\Rightarrow [(q_1\land q_2)\to q_2] $$ y $$ S(k) : [q_1\to q_2]\land[q_2\to q_3]\land\cdots\land[q_k\to q_{k+1}]\Rightarrow[(q_1\land q_2\land\cdots\land q_k)\to q_{k+1}]. $$ mantener. Queda por demostrar que para cualquier declaración $p_1,p_2,\ldots,p_k,p_{k+1},p_{k+2}$ que $$ S(k+1) : [p_1\to p_2]\land[p_2\to p_3]\land\cdots\land[p_{k+1}\to p_{k+2}]\Rightarrow[(p_1\land p_2\land\cdots\land p_{k+1})\to p_{k+2}] $$ es lo siguiente. Empezando por el lado izquierdo de $S(k+1)$ , \begin {align} \text {LHS} & \equiv [p_1 \to p_2] \land\cdots\land [p_{k+1} \to p_{k+2}] \land [p_{k+1} \to p_{k+2}] \\ [0.5em] & \Downarrow\qquad \text {(definición de conjunción)} \\ [0.5em] &[[p_1 \to p_2] \land [p_2 \to p_3] \land\cdots\land [p_{k+1} \to p_{k+2}]] \land [p_{k+1} \to p_{k+2}] \\ [0.5em] & \Downarrow\qquad \text {(por $S(k)$ con cada $q_i = p_i$ )} \\ [0.5em] &[(p_1 \land p_2 \land\cdots\land p_k) \to p_{k+1}] \land [p_{k+1} \to p_{k+2}] \\ [0.5em] & \Downarrow\qquad \text {(por $S(1)$ con $q_1=p_1\land\cdots\land p_k)$ y $q_2=p_{k+1}$ )} \\ [0.5em] &[[(p_1 \land p_2 \land\cdots\land p_k) \land p_{k+1}] \to p_{k+1}] \land [p_{k+1} \to p_{k+2}] \\ [0.5em] & \Downarrow\qquad \text {(por definición de conjunción)} \\ [0.5em] &[(p_1 \land p_2 \land\cdots\land p_k \land p_{k+1}] \to p_{k+1}] \land [p_{k+1} \to p_{k+2}] \\ [0.5em] & \Downarrow\qquad \text {(ya que $a\land b\to b$ con $b=[p_{k+1}\to p_{k+2}]$ )} \\ [0.5em] &[(p_1 \land p_2 \land\cdots\land p_k \land p_{k+1}) \to p_{k+2}] \land [p_{k+1} \to p_{k+2}] \\ [0.5em] & \Downarrow\qquad \text {(ya que $a\land b\to a$ )} \\ [0.5em] &(p_1 \land p_2 \land\cdots\land p_k \land p_{k+1}) \to p_{k+2} \\ [0.5em] & \equiv \text {RHS}, \end {align} obtenemos el lado derecho de $S(k+1)$ , con lo que se completa el paso inductivo.

Por inducción matemática, para cada $n\geq 1, S(n)$ se mantiene. $\blacksquare$

Answer 2

Por lo general, no hace falta distinguir entre inducción débil e inducción fuerte. Como señalas, la diferencia es mínima. En ambas inducciones, debes probar el caso base (generalmente muy fácil o trivial). Luego, la inducción débil asume que la afirmación es verdadera para tamaño $n-1$ y debes probar que es verdadera para $n$. Con la inducción fuerte, asumes que la afirmación es verdadera para todos los $m

En la práctica, uno puede simplemente utilizar siempre la inducción fuerte (incluso si solo necesitas saber que la afirmación es verdadera para $n-1$). En el ejemplo que das, solo necesitas asumir que la fórmula es válida para el caso anterior (inducción débil). Podrías asumir que es válida para todos los casos, pero solo usar el caso anterior. Por lo que puedo ver, realmente es solo una cuestión de semántica. Hay momentos en que la inducción fuerte es realmente más útil, como cuando divides el problema en dos problemas de tamaño $n/2`, por ejemplo. Esto ocurre con frecuencia al hacer demostraciones sobre grafos donde descompones el grafo de $n$ vértices en dos subgrafos (más pequeños, pero tienes poco o ningún control sobre el tamaño exacto).