4.2: Principio de Inducción

Comenzamos por probar un teorema que es equivalente al principio de inducción.

TEOREMA 4.3. Si
(1)\(X \subseteq \mathbb{N}\)
(2)\(0 \in X\)
(3)\((\forall n \in \mathbb{N}) n \in X \Rightarrow(n+1) \in X\),

luego\[X=\mathbb{N}\] Discusión. Discutiremos por contradicción. Eso lo asumimos\(X \neq \mathbb{N}\). Que\(Y\) sea el complemento de\(X\) in\(\mathbb{N}\). Dado que no\(Y\) está vacío, tendrá un elemento mínimo. La tercera hipótesis del teorema no permitirá un elemento mínimo en\(Y\), que no sea 0, y esto es imposible por la segunda hipótesis. Por lo tanto,\(Y\) es necesariamente vacío.

Comprobante. Vamos\(X\) a satisfacer las hipótesis del teorema. \[Y=\mathbb{N} \backslash X .\]Dejemos Supongamos que no\(Y\) está vacío. Ya que\(Y \subseteq \mathbb{N}, Y\) está bien ordenado por\(\leq\). Dejar\(a \in Y\) ser el menor elemento de\(Y\). Observamos que no\(a\) es 0, ya que\(0 \in X\). Por lo tanto\(a \geq 1\) y es un sucesor, así\(a-1\) es en\(\mathbb{N}\) y no en\(Y\). De ahí\(a-1\) está en\(X\). Pero luego por hipótesis (3) del teorema,\(a-1+1 \in X\). Esto es una contradicción, por lo tanto\(Y\) está vacío y\(X=\mathbb{N}\).

OBSERVACIÓN. Ocasionalmente incluiremos discusiones informales etiquetadas en nuestras pruebas para guiarte en tu lectura. Esta no es una práctica habitual. No debe incluir tales discusiones en sus pruebas a menos que su instructor lo solicite.

El teorema\(4.3\) se aplica más fácilmente en la siguiente forma.

COROLARIO 4.4. Principio de inducción Dejar\(P(x)\) ser una fórmula en una variable. Si

(1)\(P(0)\)

(2)\((\forall x \in \mathbb{N}) P(x) \Rightarrow P(x+1)\),

después\[(\forall x \in \mathbb{N}) P(x) .\] Prueba. Que\[\chi_{P}=\{x \in \mathbb{N} \mid P(x)\} .\] Deseemos demostrar eso\(\chi_{P}=\mathbb{N}\). Por suposición (1),\(P(0)\), entonces\(0 \in \chi_{P}\). Asumir eso\(n \in \chi_{P}\). Entonces\(P(n)\). Por suposición (2)\[P(n) \Rightarrow P(n+1) .\] Por lo tanto\(P(n+1)\) y\(n+1 \in \chi_{P}\). Ya que\(n\) es arbitrario,\[(\forall n \in \mathbb{N}) n \in \chi_{P} \Rightarrow n+1 \in \chi_{P} .\] Por Teorema 4.3,\(\chi_{P}=\mathbb{N}\) y\[(\forall x \in \mathbb{N}) P(x)\] Supongamos que se desea demostrar que una fórmula\(P(x)\) sostiene para todos los números naturales. Al argumentar por inducción, el autor debe demostrar que las hipótesis para el teorema están satisfechas. Normalmente, el autor primero lo demuestra\(P(0)\). A esto se le llama el caso base de la prueba por inducción. Muy a menudo es una conclusión fácil, incluso trivial. No obstante, es necesario probar un caso base para poder argumentar por inducción (¿se puede demostrar esto?). Habiendo probado el caso base, el autor probará entonces la segunda hipótesis, a saber, que la afirmación de ser cierta para un número natural arbitrario implica que es cierto en el sucesor de ese número natural. Este es el paso de inducción. El paso de inducción requiere probar una declaración condicional, que a menudo se prueba directamente. Es importante entender que el autor no está alegando que\(P\) sostiene en un número natural arbitrario, de lo contrario el argumento sería circular e inválido. Más bien, el autor demostrará que si el resultado fuera cierto en un número natural arbitrario, entonces sería cierto para el número natural posterior. El supuesto que se\(P\) sostiene en un número natural fijo y arbitrario se denomina hipótesis de inducción. Si el autor prueba con éxito el caso base y el paso de inducción, entonces\(4.4\) se satisfacen los supuestos de Corolario, y\(P\) mantiene en todos los números naturales.

Proposición 4.5. Vamos\(N \in \mathbb{N}\). Después\[\sum_{n=0}^{N} n=\frac{N(N+1)}{2} .\] Discusión. Este es un buen primer ejemplo de una prueba por inducción. El argumento es una aplicación directa de la técnica y el resultado es de interés histórico y práctico. Argumentamos por inducción en el índice superior de la suma. Es decir, la fórmula que estamos probando para todos los números naturales es\[P(x): \sum_{n=0}^{x} n=\frac{x(x+1)}{2} .\] Es importante identificar la cantidad sobre la que se está aplicando el principio de inducción, pero algunos autores que están escribiendo un argumento para lectores que están familiarizados con la inducción pueden no declarar explícitamente la fórmula.

Demostramos un caso base\(N=0\),, que corresponde a la suma con el término único 0. Luego argumentamos el paso de inducción. Este es nuestro primer argumento utilizando el principio de inducción. Preste mucha atención a la estructura de esta prueba. Debes esforzarte por seguir las convenciones de pruebas por inducción que establecemos en este libro.

Comprobante. Caso base:\(N=0\).

Discusión. Tenga en cuenta que el caso base es la declaración\(P(0)\).

Ya que\[\sum_{n=0}^{0} n=0=\frac{(0)(1)}{2},\]\(P(0)\) sostiene.

Paso de inducción:

Discusión. Demostramos la afirmación universal\[(\forall x \in \mathbb{N}) P(x) \Rightarrow P(x+1) .\] demostrando que para un número natural arbitrario\(N\)\[P(N) \Rightarrow P(N+1) .\] Así reducimos probar una declaración universal a probar una declaración condicional abstracta. Demostramos directamente la declaración condicional resultante. Es decir, asumimos\(P(N)\) y derivamos\(P(N+1)\). Le recordamos al lector que no estamos reclamando que el resultado se mantenga en\(N\) - es decir, no reclamamos\(P(N)\). Más bien, estamos demostrando la afirmación condicional asumiendo el antecedente, la hipótesis de inducción y derivando la consecuencia. Si no usas la hipótesis de inducción, no estás discutiendo por inducción. Desde luego, en el cuerpo del argumento esto es transparente, sin referencia a los principios lógicos subyacentes.

Dejemos\(N \in \mathbb{N}\) y supongamos que\[\sum_{n=0}^{N} n=\frac{N(N+1)}{2} .\] Entonces\[\begin{aligned} \sum_{n=0}^{N+1} n &=\left(\sum_{n=0}^{N} n\right)+N+1 \\ &={ }_{I H} \frac{N(N+1)}{2}+N+1 \end{aligned}\] por la hipótesis de inducción.

Discusión. Es un buen hábito, y una consideración para tu lector, identificar cuándo estás invocando la hipótesis de inducción. Utilizaremos el subíndice\({ }_{I H}\) para indicar dónde invocamos la hipótesis de inducción.

Entonces,\[\begin{aligned} \sum_{n=0}^{N+1} n &=\frac{N(N+1)}{2}+N+1 \\ &=\frac{N(N+1)}{2}+\frac{2 N+2}{2} \\ &=\frac{N^{2}+3 N+2}{2} \\ &=\frac{(N+1)((N+1)+1)}{2} . \end{aligned}\]\[(\forall N \in \mathbb{N}) P(N) \Rightarrow P(N+1) .\] Por el principio de inducción, sigue la proposición.

Proposición 4.6. Vamos\(N \in \mathbb{N}\). Después\[\sum_{n=0}^{N} n^{2}=\frac{N(N+1)(2 N+1)}{6} .\] Prueba. La aseveración\(P(N)\) es que la ecuación (4.7) sostiene. El caso base,\(N=0\), es obvio: Paso\[\sum_{n=0}^{0} n^{2}=\frac{0(0+1)(2 \cdot 0+1)}{6} .\] de inducción:

Asumir eso\(N \in \mathbb{N}\) y\[\sum_{n=0}^{N} n^{2}=\frac{N(N+1)(2 N+1)}{6}\] Demostramos que\[\sum_{n=0}^{N+1} n^{2}=\frac{(N+1)(N+2)(2 N+3)}{6}\] Efectivamente\[\begin{aligned} \sum_{n=0}^{N+1} n^{2} &=\left(\sum_{n=0}^{N} n^{2}\right)+(N+1)^{2} \\ &=I H \\ &=\frac{N(N+1)(2 N+1)}{6}+(N+1)^{2} . \\ &=\frac{N(N+1)(2 N+1)}{6}+(N+1)^{2} \\ &=\frac{2 N^{3}+9 N^{2}+13 N+6}{6} \\ & \frac{(N+1)(N+2)(2(N+1)+1)}{6} . \end{aligned}\] La proposición se desprende del principio de inducción.

Discusión. La prueba de la Proposición\(4.6\) es muy similar a la prueba de la Proposición 4.5. Es posible que desee confirmar las identidades algebraicas en la última parte de la prueba, ya que no son obvias. Se incluye solo el detalle suficiente para guiarlo a través de la prueba de la implicación. El autor de una prueba por inducción asumirá que te sientes cómodo con la técnica, y con ello puede proporcionar menos detalles de los que te gusta.

OBSERVACIÓN. Hay más en las Proposiciones\(4.5\) y\(4.6\) que solo las pruebas. También están las fórmulas. En efecto, un uso de la inducción es que si adivina una fórmula, puede usar la inducción para demostrar que su fórmula es correcta. Ver Ejercicios\(4.12\) y 4.16.

¿Por qué es necesario un caso base? Considera el siguiente argumento a favor de la falsa afirmación\(\sum_{n=0}^{N} n<\frac{N(N+1)}{2}\). Vamos\(N \in \mathbb{N}\) y supongamos\(P(N)\), donde\(P(N)\) esta la declaracion\[\sum_{n=0}^{N} n<\frac{N(N+1)}{2} .\] Entonces\[\begin{aligned} \sum_{n=0}^{N+1} n &=\left(\sum_{n=0}^{N} n\right)+N+1 \\ <_{I H} & \frac{N(N+1)}{2}+N+1 \\ &=\frac{N^{2}+3 N+2}{2} \\ &=\frac{(N+1)((N+1)+1)}{2} . \end{aligned}\] De ahí, Por\[(\forall N \in \mathbb{N}) P(N) \Rightarrow P(N+1) .\] supuesto que la desigualdad\(P(N)\) se demuestra fácilmente como falsa. ¿Qué salió mal? Sin un caso base, probar no\[(\forall N \in \mathbb{N}) P(N) \Rightarrow P(N+1)\] es suficiente para probar\((\forall N \in \mathbb{N}) P(N)\). Si\(P(0)\) fuera verdad, entonces\(P(1)\) sería verdad, y si\(P(1)\) fuera verdad, entonces lo\(P(2)\) sería, y así sucesivamente. En efecto, si somos capaces de probar\(P(N)\) para alguno\(N \in \mathbb{N}\), entonces sabemos\(P(M)\) por cualquier número natural\(M>N\). Pero la secuencia de declaraciones\(\langle P(0), P(1), P(2), \ldots\rangle\) nunca se inicia. \(P(N)\)falla para todos\(N\).

Otra forma de pensar en la inducción es en términos de garantías. Supongamos que decide comprar un auto. Primero vas a Honest Bob's Bob garantiza que cualquier auto que venda irá por lo menos a una milla. Se compra un auto, lo sacas del lote, y después de 3 millas se descompone y no se puede arreglar. Regresas con enojo, pero Bob no te devolverá tu dinero porque el auto estuvo a la altura de la garantía.

Entonces cruzas la carretera hacia Honest John's John garantiza que si te vende un auto, una vez que arranca nunca se detendrá. Esto suena bastante bien, así que compras un auto, pones las llaves en el encendido, y... nada. El auto no arranca. John tampoco te devolverá tu dinero, porque el auto no dejó de hacer lo que reclamó.

Sentirse desesperado, terminas en Honest Stewart's Los autos de Stewart vienen con dos garantías:

(1) El auto arrancará y recorrerá al menos una milla.

(2) No importa qué tan lejos haya ido el auto, siempre se puede conducir una milla extra.

Piensas esto de nuevo, y finalmente decides que el auto irá para siempre. Lo mejor de todo es que el arrendamiento es de solo\(\$ 1\) un mes por los dos primeros meses. Firmas el contrato de arrendamiento y conduces a casa bastante satisfecho contigo mismo. \({ }^{1}\)

Hay muchas generalizaciones útiles del principio de inducción. El primero que discutimos se llama inducción fuerte. Se llama así porque la hipótesis de inducción es más fuerte que la hipótesis de inducción en la inducción estándar, y por lo tanto el paso de inducción a veces es más fácil de probar en un argumento por inducción fuerte.

COROLARIO 4.8. Inducción fuerte Deja\(P(x)\) que sea una fórmula tal que

\({ }^{1}\)Tienes razón en que el Principio de Inducción garantiza que tu auto conducirá para siempre. No obstante, como señala tu madre cuando le muestras el contrato de arrendamiento, después de los dos primeros meses tu pago cada mes es la suma de tus pagos en los dos meses anteriores. ¿Cuánto vas a pagar después de 5 años? (1)\(P(0)\)

(2) Para cada uno\(n \in \mathbb{N}\),\[[(\forall x<n) P(x)] \Rightarrow[P(n)]\] entonces\[(\forall x \in \mathbb{N}) P(x)\] Intuitivamente esto no es muy diferente de la inducción básica. Empiezas en un caso base, y una vez iniciado puedes continuar por el resto de los números naturales. La distinción está justo en el número de suposiciones que usas al momento de probar algo por fuerte inducción. En la práctica, da la ventaja de que en el paso de inducción se puede reducir caso\(N\) a cualquier caso anterior, en lugar del caso inmediatamente anterior,\(N-1\). En particular, esto simplifica los argumentos sobre la divisibilidad y los enteros.

Discusión. Reducimos el principio de inducción fuerte al principio de inducción. Esto lo logramos introduciendo una fórmula\(Q(x)\), que dice: “P (y) es cierto para todos\(y<x "\). La inducción fuerte\(P(x)\) es equivalente a la inducción básica en\(Q(x) .\)

PRUEBA. Supongamos que\(P(x)\) satisface las hipótesis del corolario. \(Q(x)\)Sea la fórmula\[(\forall y \leq x) P(y)\] donde\(y\) está el universo de\(\mathbb{N}\). Entonces\(Q(0) \equiv P(0)\), así es cierto. Vamos\(N \in \mathbb{N}\),\(N \geq 1\), y asumir\(Q(N)\). Entonces\[(\forall y \leq N) P(y)\] y por lo tanto\(P(N+1)\). De ahí\[(\forall n \leq N+1) P(y)\] y así\(Q(N+1)\). Por lo tanto\[(\forall x \in \mathbb{N}) Q(x) \Rightarrow Q(x+1)\] Por el principio de inducción,\[(\forall x \in \mathbb{N}) Q(x) .\] Sin embargo, para cualquier\(N \in \mathbb{N}, Q(N) \Rightarrow P(N)\), por lo que la inducción\[(\forall x \in \mathbb{N}) P(x) .\] Fuerte es particularmente útil a la hora de probar afirmaciones sobre división. Hay ejemplos de la técnica a lo largo del Capítulo 7. Los resultados en el Capítulo 7 no requieren el Capítulo 5 y el Capítulo 6, por lo que fácilmente puede saltarse adelante. Véase por ejemplo la Sección 7.1, donde se prueba el Teorema Fundamental de Aritemética mediante inducción fuerte. La inducción no tiene que comenzar en 0, ni siquiera en un número natural.

COROLARIO 4.9. Dejar\(k \in \mathbb{Z}\), y\(P(x)\) ser una fórmula en una variable tal que

(1)\(P(k)\)

(2)\((\forall x \geq k) P(x) \Rightarrow P(x+1)\).

Después\[(\forall x \in \mathbb{Z}) x \geq k \Rightarrow P(x)\] Discusión. Esto se puede probar definiendo una nueva fórmula que se puede probar con inducción estándar. ¿Se puede definir la fórmula?