¿Cuál es la diferencia entre la inducción simple y la inducción fuerte?

Question

Acabo de empezar a aprender la inducción en mi curso de primer año. Me está costando mucho entender el concepto. Creo que entiendo lo básico, pero ¿podría alguien explicarme el resumen de la inducción simple y la inducción fuerte y cuáles son las diferencias? El video que estoy viendo explica que si P(k) es cierto, entonces P(k+1) es cierto para la inducción simple, y para la inducción fuerte si P(i) es cierto para todos los i menos que igual a k entonces P(k+1) es cierto. No sé realmente lo que eso significa.

Answer 1

Con la inducción simple se utiliza "si $p(k)$ es verdadero, entonces $p(k+1)$ es verdadero" mientras que en la inducción fuerte se utiliza "si $p(i)$ es cierto para todos los $i$ menor o igual a $k$ entonces $p(k+1)$ es verdadero", donde $p(k)$ es alguna afirmación que depende del número entero positivo $k$ .

NO son "idénticos" pero son equivalentes.

Es fácil ver que si la inducción simple es verdadera, entonces la inducción fuerte es verdadera: si se sabe que la afirmación $p(i)$ es cierto para todos los $i$ menor o igual a $k$ entonces sabes que es cierto, en particular, para $i=k$ y puede utilizar la inducción simple.

Es más difícil de demostrar, pero sigue siendo cierto, que si la inducción fuerte es verdadera, entonces la inducción simple es verdadera. Eso es lo que queremos decir con "equivalente".

Aquí tenemos una pregunta. No se trata de por qué seguimos teniendo una inducción "débil", sino de por qué seguimos teniendo una inducción "fuerte" cuando ésta no es realmente más fuerte.

Mi opinión es que la razón por la que se mantiene esta distinción es que sirve a un propósito pedagógico. Las primeras pruebas por inducción que enseñamos suelen ser cosas como $\forall n\left[\sum_{i=0}^n i= \frac{n(n+1)}{2}\right]$ . Las pruebas de éstas sugieren naturalmente la inducción "débil", que los estudiantes aprenden como patrón a imitar.

Más adelante, enseñamos pruebas más difíciles en las que ese patrón ya no funciona. Para dar un nombre a la diferencia, llamamos al nuevo patrón "inducción fuerte", de modo que podamos distinguir entre los métodos al presentar una demostración en una clase. Así podemos decir a un alumno "intente usar la inducción fuerte", lo que es más útil que "intente usar la inducción".

Answer 2

Un ejemplo del uso de la inducción fuerte es la prueba inductiva de que cualquier primo $p\not \equiv 3 \pmod 4$ es la suma de cuadrados de dos enteros. Tenemos $2=1^2+1^2.$ Para la primera $p\equiv 1 \pmod 4,$ en algún momento de la prueba tenemos que emplear la hipótesis inductiva de que todo primo $q$ tal que $p>q\not \equiv 3 \pmod 4$ es la suma de dos cuadrados, porque (después de un buen rato de trabajo) tal $q$ aparece en el álgebra pero no sabemos cuál es.