9.3: Prueba por inducción

Uno de los métodos de prueba más poderosos —y uno de los más difíciles de entender— se llama inducción matemática, o simplemente “inducción” para abreviar. A mí me gusta llamarlo “prueba por recursión”, porque esto es exactamente lo que es. Recuerde que discutimos la recursión en el contexto de árboles enraizados (ver p.5.2). Un árbol puede pensarse como un nodo con varios hijos, cada uno de los cuales es, a su vez, árboles. Cada uno de ellos es el nodo raíz de un árbol compuesto por árboles aún más pequeños, y así sucesivamente y así sucesivamente. Si volteas hacia el lado izquierdo de la Figura 5.2.2 en la p.5.2, verás que A es la raíz de un árbol, y sus dos hijos, F y B, son raíces de sus propios árboles más pequeños a su vez. Si atravesáramos este árbol en (digamos) pre-orden, visitaríamos la raíz, luego visitaríamos los subárboles izquierdo y derecho a su vez, tratando a cada uno de ellos como su propio árbol. De esta manera hemos dividido un problema mayor (atravesar el árbol grande) en problemas más pequeños (atravesar los árboles más pequeños F y B). El nodo A tiene muy poco que hacer: simplemente se visita a sí mismo, luego aplaza todo el resto del trabajo sobre sus hijos. Esta idea de empeñar la mayor parte del trabajo en subproblemas más pequeños en los que confías que funcionarán es clave para la idea de pruebas inductivas.

La inducción matemática es difícil de entender porque se siente como hacer trampa. Parece que en realidad nunca demuestras nada: aplaza todo el trabajo a otra persona, y luego declaras la victoria. Pero la cadena del razonamiento, aunque delicada, es fuerte como el hierro.

Cómo lanzar el problema en la forma correcta

Examinemos esa cadena. Lo primero que tienes que hacer es expresar lo que intentas demostrar como predicado sobre los números naturales. En otras palabras, es necesario formar un predicado que tenga una entrada, que es un número natural. Te estás configurando para demostrar que el predicado es cierto para todos los números naturales. (O al menos, todos los números naturales de al menos un cierto tamaño.)

Supongamos que quiero probar que en el estado de Virginia, todos los bebedores legales pueden votar. Entonces podría decir “que Vote (\(n\)) sea la proposición de que un ciudadano mayor de edad\(n\) pueda votar”.

Si quiero probar una identidad algebraica, como\(\sum_{i=1}^x{i} = \frac{x(x+1)}{2}\), entonces tengo que averiguar qué variable es la que necesita variar entre los números naturales. En este caso es la\(x\) variable en mi ecuación. Entonces voy a decir “deja que P (\(n\)) sea la proposición que”\(\sum_{i=1}^n{i} = \frac{n(n+1)}{2}\). (La elección de la letra “\(n\)" no es importante aquí —solo tiene que ser una letra que signifique un número. Podríamos haber elegido cualquier cosa, incluso seguir con él\(x\). Más tarde, usaremos “\(k\)" como un stand-in, así que mantén los ojos bien abiertos para eso).

Si quiero demostrar que el número de hojas en un árbol binario perfecto es uno más que el número de nodos internos, tendría que pensar en qué cantidad puedo parametrizar (es decir, qué cantidad puedo usar para mi\(n\).) En este caso, probablemente usaría la altura del árbol. Yo diría “que P (\(n\)) sea la proposición de que el número de hojas en un árbol binario perfecto de altura\(n\) es una más que el número de nodos internos”.

Estos son solo ejemplos. En cualquier caso, es necesario emitir su comprobante en una forma que le permita hacer declaraciones en términos de los números naturales. Entonces estás listo para comenzar el proceso de probar por inducción que tu predicado es cierto para todos los números naturales.

Prueba por inducción: forma débil

En realidad hay dos formas de inducción, la forma débil y la forma fuerte. Veamos primero la forma débil. Dice:

1. Si un predicado es cierto para un cierto número,

2. y que sea cierto para algún número significaría de manera confiable que también es cierto para el siguiente número (es decir, un número mayor),

3. entonces es cierto para todos los números.

Todo lo que tienes que hacer es probar esas dos cosas, y lo has probado efectivamente para cada caso.

El primer paso se llama el caso base, y el “cierto número” que elegimos normalmente es 0 o 1. El segundo paso, llamado el paso inductivo, es donde yace todo el problema. Hay que mirar muy, muy cuidadosamente cómo está redactado, arriba. ¡No estamos asumiendo que el predicado es cierto para cualquier número antiguo! Simplemente estamos considerando, si es cierto para cualquier número antiguo, si eso implicaría necesariamente que también es cierto para el siguiente número. En cuanto al predicado, estamos preguntando “¿P (\(k\)) implica P (\(k+1\))?” En otras palabras: “no estamos seguros si P (\(k\)) es cierto. Pero si lo hace, un gran “si”, por supuesto, ¿eso exigiría lógicamente que P (\(k+1\)) también fuera cierto?” Si puedes probar que lo hace, entonces estás en el negocio.

Todo está configurado como una fila de dominó. Si cae un dominó, entonces el que viene después también caerá. Y si ese cae, entonces también lo hará el siguiente. Todo lo que se necesita es un caso base para volcar el primer dominó, y por este rastro de causalidad, todos los dominó caerán.

Una nota terminológica: todo el segundo paso se llama el paso inductivo, pero la primera mitad del mismo (la parte donde suponemos que P (\(k\)) es verdadera) se llama hipótesis inductiva. Nunca probamos la hipótesis inductiva; más bien, la asumimos, y luego vemos si eso nos permite deducir que P (\(k+1\)) también sería cierto.

Ejemplo 1

Vamos a resolverlo para el ejemplo de beber/votar. Que Vote (\(n\)) sea la proposición de que un ciudadano mayor de edad\(n\) pueda votar. Nuestra prueba va así:

1. estuche base. El voto (21) es cierto, porque un joven de 21 años tiene la edad suficiente para votar en las elecciones estatales y nacionales.

2. paso inductivo. Votación k\(\Rightarrow\) Voto (k+1). ¿Por qué? Porque nadie se está poniendo más joven. Si puedes votar en un año en particular, entonces también tienes la edad suficiente para votar el próximo año. A menos que cambien las leyes, nunca habrá un caso en el que alguien lo suficientemente mayor para votar este año resulte ser demasiado joven para votar el próximo año.

3. Guau. Ya terminamos. Q.E.D. y todo eso.

El único ejemplo específico que mostramos fue cierto fue Vote (21). Y sin embargo logramos probar Vote (\(n\)) para cualquier número\(n\geq21\).

Echemos un vistazo a ese paso inductivo, porque ahí es donde está toda la acción. Es crucial entender lo que ese paso no dice. No dice “Votar (\(k\)) es cierto para algún número”\(k\). Si lo hiciera, entonces dado que\(k\) el valor de's es arbitrario en ese momento, básicamente estaríamos asumiendo lo mismo que se suponía que debíamos probar, que es el razonamiento circular y extremadamente poco convincente. Pero eso no es lo que hicimos. En cambio, hicimos la hipótesis inductiva y dijimos: “bien entonces, supongamos por un segundo que un niño de 40 años puede votar. No lo sabemos con certeza, pero digamos que puede. Ahora bien, si eso es cierto, ¿puede votar también un niño de 41 años? La respuesta es sí”. Podríamos haber dicho: “bien entonces, supongamos por un segundo que un niño de 7 años puede votar. No lo sabemos con certeza, pero digamos que puede. Ahora bien, si eso es cierto, ¿puede votar también un niño de 8 años? La respuesta es sí”. ¡Observe cuidadosamente que no dijimos que los niños de 8 años puedan votar! Simplemente dijimos que si los niños de 7 años pueden, por qué entonces los de 8 años también deben poder hacerlo. Recuerda que X\(\Rightarrow\) Y es verdadero si X es falso o Y es verdadero (o ambos). En el ejemplo de 7/8 años, la premisa X resulta ser falsa, por lo que esto no descarta nuestra implicación.

El resultado es una fila de dominó cayendo, hasta el número que queramos. Digamos que queremos verificar que un joven de 25 años pueda votar. ¿Podemos estar seguros? Bien:

1. Si un joven de 24 años puede votar, entonces eso seguro lo probaría (por el paso inductivo).

2. Entonces ahora tenemos que verificar que un joven de 24 años pueda votar. ¿Puede él? Bueno, si un joven de 23 años puede votar, entonces eso seguro lo probaría (por el paso inductivo).

3. Ahora todo depende de si un joven de 23 años puede votar. ¿Puede él? Bueno, si un joven de 22 años puede votar, entonces eso seguro lo probaría (por el paso inductivo).

4. Entonces, se reduce a si un joven de 22 años puede votar. ¿Puede él? Bueno, si un joven de 21 años puede votar, entonces eso seguro lo probaría (por el paso inductivo).

5. Y ahora tenemos que verificar si un joven de 21 años puede votar. ¿Puede él? Sí (por el caso base).

Ejemplo 2

Una famosa historia cuenta de Carl Friedrich Gauss, quizás el matemático más brillante de todos los tiempos, metiéndose en problemas algún día como colegial. Como castigo, fue sentenciado a un trabajo tedioso: sumar todos los números del 1 al 100. Para asombro de su maestro, se le ocurrió la respuesta correcta en un momento, no porque fuera rápido en sumar enteros, sino porque reconoció un truco. El primer número de la lista (1) y el último (100) suman 101. Así lo hacen el segundo número (2) y el penúltimo (99). Así hacen 3 y 98, y así lo hacen 4 y 97, etc., hasta el 50 y 51. Entonces realmente lo que tienes aquí son 50 sumas diferentes de 101 cada una, así que la respuesta es\(50\times 101 = 5050\). En general, si agregas los números del 1 al\(x\), donde\(x\) está cualquier entero en absoluto, obtendrás\(\frac{x}{2}\) sumas de\(x+1\) cada uno, por lo que la respuesta será\(\frac{x(x+1)}{2}\).

Ahora, usa la inducción matemática para probar que Gauss tenía razón (es decir, eso\(\sum_{i=1}^x{i} = \frac{x(x+1)}{2}\)) para todos los números\(x\).

Primero tenemos que lanzar nuestro problema como predicado sobre los números naturales. Esto es fácil: decimos “que P (\(n\)) sea la proposición que”\(\sum_{i=1}^n{i} = \frac{n(n+1)}{2}\).

Entonces, satisfacemos los requisitos de inducción:

1. estuche base. Demostramos que P (1) es cierto simplemente enchufándolo. Configuración\(n=1\) que tenemos\[\begin{aligned} \sum_{i=1}^1{i} & \stackrel{?}{=} \frac{1(1+1)}{2} \\ 1 & \stackrel{?}{=} \frac{1(2)}{2} \\ 1 &= 1 \quad \checkmark\end{aligned}\]

2. paso inductivo. Ahora debemos probar que P (\(k\))\(\Rightarrow\) P (\(k+1\)). Dicho de otra manera, asumimos que P (\(k\)) es cierto, y luego usamos esa suposición para probar que P (\(k+1\)) también es cierto.

   Seamos claros como el cristal a dónde vamos con esto. Asumiendo que P (\(k\)) es cierto significa que podemos contar con el hecho de que\[\begin{aligned} 1+2+3+\cdots+k = \frac{k(k+1)}{2}.\end{aligned}\]

   Lo que tenemos que hacer, entonces, es probar que P (\(k+1\)) es cierto, lo que equivale a probar que\[\begin{aligned} 1+2+3+\cdots+(k+1) = \frac{(k+1)((k+1)+1)}{2}.\end{aligned}\]

   Muy bien. Primero hacemos la hipótesis inductiva, que nos permite asumir:\[\begin{aligned} 1+2+3+\cdots+k = \frac{k(k+1)}{2}.\end{aligned}\] El resto es solo álgebra. Agregamos\(k+1\) a ambos lados de la ecuación, luego multiplicamos las cosas y las factorizamos todas juntas. Observe cuidadosamente:\[\begin{aligned} 1+2+3+\cdots+k+(k+1) &= \frac{k(k+1)}{2} + (k+1) \\ &= \frac{1}{2}k^2 + \frac{1}{2}k + k + 1 \\ &= \frac{1}{2}k^2 + \frac{3}{2}k + 1 \\ &= \frac{k^2+3k+2}{2} \\ &= \frac{(k+1)(k+2)}{2} \\ &= \frac{(k+1)((k+1)+1)}{2}. \quad \checkmark\end{aligned}\]

Por lo tanto,\(\forall n\geq1 \ \text{P}(n)\).

Ejemplo 3

Otro álgebra. Aprendiste eso en la secundaria\((ab)^n=a^n b^n\). Demuéstralo por inducción matemática.

Solución: Que P (\(n\)) sea la proposición que\((ab)^n=a^n b^n\).

1. estuche base. Demostramos que P (1) es cierto simplemente enchufándolo. Configuración\(n=1\) que tenemos\[\begin{aligned} (ab)^1 &= \stackrel{?}{=} a^1 b^1 \\ ab &= ab \quad \checkmark\end{aligned}\]

2. paso inductivo. Ahora debemos probar que P (\(k\))\(\Rightarrow\) P (\(k+1\)). Dicho de otra manera, asumimos que P (\(k\)) es cierto, y luego usamos esa suposición para probar que P (\(k+1\)) también es cierto.

   Seamos claros como el cristal a dónde vamos con esto. Asumiendo que P (\(k\)) es cierto significa que podemos contar con el hecho de que\[\begin{aligned} (ab)^k = a^k b^k.\end{aligned}\]

   Lo que tenemos que hacer, entonces, es probar que P (\(k+1\)) es cierto, lo que equivale a probar que\[\begin{aligned} (ab)^{k+1} = a^{k+1} b^{k+1}.\end{aligned}\]

   Ahora sabemos por la definición misma de exponentes que:\[\begin{aligned} (ab)^{k+1} &= ab(ab)^k. \\\end{aligned}\]

   Añadiendo en nuestra hipótesis inductiva entonces nos permite determinar:\[\begin{aligned} (ab)^{k+1} &= ab(ab)^k \\ &= ab \cdot a^k b^k \\ &= a \cdot a^k \cdot b \cdot b^k \\ &= a^{k+1} b^{k+1} \quad \checkmark\end{aligned}\]

Por lo tanto,\(\forall n\geq1 \ \text{P}(n)\).

Ejemplo 4

Cambiemos de marcha y hablemos de estructuras. Demostrar que el número de hojas en un árbol binario perfecto es uno más que el número de nodos internos.

Solución: dejar que P (\(n\)) sea la proposición de que un árbol binario perfecto de altura\(n\) tiene una hoja más que un nodo interno. Es decir, si\(l_k\) es el número de l aleros en un árbol de altura\(k\), y\(i_k\) es el número de nodos internos en un árbol de altura\(k\), que P (\(n\)) sea la proposición de que \(l_n = i_n + 1\).

1. estuche base. Demostramos que P (0) es cierto simplemente por inspección. Si tenemos un árbol de altura 0, entonces solo tiene un nodo (la raíz). Este único nodo es una hoja, y no es un nodo interno. Entonces este árbol tiene 1 hoja, y 0 nodos internos, y así\(l_0 = i_0 + 1\).

2. paso inductivo. Ahora debemos probar que P (\(k\))\(\Rightarrow\) P (\(k+1\)). Dicho de otra manera, asumimos que P (\(k\)) es cierto, y luego usamos esa suposición para probar que P (\(k+1\)) también es cierto.

   Seamos claros como el cristal a dónde vamos con esto. Asumiendo que P (\(k\)) es cierto significa que podemos contar con el hecho de que\[\begin{aligned} l_k = i_k + 1.\end{aligned}\]

   Lo que tenemos que hacer, entonces, es probar que P (\(k+1\)) es cierto, lo que equivale a probar que\[\begin{aligned} l_{k+1} = i_{k+1} + 1.\end{aligned}\]

   Comenzamos por señalar que el número de nodos a nivel \(k\)de un árbol binario perfecto es\(2^k\). Esto se debe a que la raíz es solo un nodo, tiene dos hijos (dando 2 nodos en el nivel 1), ambos esos hijos tienen dos hijos (dando 4 nodos en el nivel 2), los cuatro de esos hijos tienen dos hijos (dando 8 nodos en el nivel 3), etc. por lo tanto,\(l_k = 2^k\), y \(l_{k+1} = 2^{k+1}\).

   Además, observamos que\(i_{k+1} = i_k + l_k\): así es como funcionan los árboles. En palabras, supongamos que tenemos un árbol binario perfecto de altura\(k\), y le agregamos otro nivel de nodos, convirtiéndolo en un árbol binario perfecto de altura\(k+1\). Entonces todos los nodos del primer árbol (ya sean internos u hojas) se convierten en nodos internos de árbol más grande.

   Combinando estos dos hechos, tenemos\(i_{k+1} = i_k + 2^k\). Por la hipótesis inductiva, asumimos eso\(2^k = i_k + 1\), y ahora debemos probarlo\(2^{k+1} = i_{k+1} + 1\). Aquí va:\[\begin{aligned} n_{k+1} &= n_k + 2^k &(property\space of\space trees) \\ n_{k+1} &= 2^k - 1 + 2^k &(using\space inductive\space hypothesis) \\ n_{k+1} + 1 &= 2^k + 2^k \\ n_{k+1} + 1 &= 2(2^k) \\ n_{k+1} + 1 &= 2^{k+1}. \quad \checkmark\end{aligned}\]

Por lo tanto,\(\forall n\geq0 \ \text{P}(n)\).

Prueba por inducción: forma fuerte

Ahora a veces en realidad necesitamos hacer una suposición más fuerte que solo “la única proposición P (\(k\)) es verdadera” para demostrar que P (\(k+1\)) es verdad. En todos los ejemplos anteriores, el\(k+1\) caso fluyó directamente del\(k\) caso, y solo del\(k\) caso. Pero a veces, hay que saber que todos los casos menos que\(k+1\) son ciertos para poder probar el\(k+1\) caso. En esas situaciones, utilizamos la forma fuerte de inducción matemática. Dice:

1. Si un predicado es verdadero para un número determinado,

2. y que sea cierto para todos los números hasta e incluyendo algún número significaría de manera confiable que también es cierto para el siguiente número (es decir, un número mayor),

3. entonces es cierto para todos los números.

Es exactamente lo mismo que la forma débil, salvo que la hipótesis inductiva es más fuerte. En lugar de tener que probar

P (\(k\))\(\Rightarrow\) P (\(k+1\)),

llegamos a probar

(\(\forall i\leq k\)P (\(i\)))\(\Rightarrow\) P (\(k+1\)).

A primera vista eso podría no parecer más fácil. Pero si miras con atención, puedes ver que hemos agregado información al lado izquierdo de la implicación. Ya no necesitamos confiar en el único hecho de que P (5) es cierto para probar P (6). Ahora llegamos a aprovechar que P (1), P (2), P (3), P (4) y P (5) son todos conocidos como verdaderos cuando tratamos de probar P (6). Y eso puede hacer un mundo de diferencia.

Ejemplo 1

El Teorema Fundamental de la Aritmética dice que cada número natural (mayor que 2) es expresable como producto de uno o más primos. Por ejemplo, 6 puede escribirse como\(2 \cdot 3\) ““, donde 2 y 3 son primos. El número 7 es en sí mismo primo, y así se puede escribir como “\(7\).” El número 9,180 se puede escribir como “\(2 \cdot 2 \cdot 3 \cdot 3 \cdot 3 \cdot 5 \cdot 17\),” todos los cuales son primos. ¿Cómo podemos probar que esto siempre es posible, sin importar cuál sea el número?

Sea P (\(n\)) la proposición de que el número\(n\) puede expresarse como un producto de números primos. Nuestra prueba va así:

1. estuche base. P (2) es cierto, ya que 2 puede escribirse como “2", y 2 es un número primo. (Tenga en cuenta que no usamos 0 o 1 como nuestro caso base aquí, ya que en realidad ninguno de esos números es expresable como producto de primos. Dato curioso.)

2. paso inductivo. Ahora debemos probar que (\(\forall i \leq k\)P (\(k\)))\(\Rightarrow\) P (\(k+1\)). Dicho de otra manera, asumimos que P (\(i\)) es cierto para cada número hasta\(k\), y luego usamos esa suposición para probar que P (\(k+1\)) también es cierto.

   En cuanto al número\(k+1\), hay dos posibilidades: o es primo, o no lo es. Si lo es, entonces ya terminamos, porque obviamente puede escribirse como solo en sí mismo, que es producto de un primo. (23 se puede escribir como “23”.) Pero supongamos que no lo es. Entonces, se puede desglosar como el producto de dos números, cada uno menos que él mismo. (21 se puede desglosar como\(7 \cdot 3\); 24 se puede desglosar como\(6 \cdot 4\) o\(12 \cdot 2\) o\(8 \cdot 3\), elige tu elección.) Ahora no sabemos nada especial de esos dos números... excepto el hecho de que la hipótesis inductiva nos dice que todos los números menores que\(k+1\) son expresables como producto de uno o más primos! Entonces estos dos números, sean cuales sean, son expresables como producto de primos, y así cuando los multipliques juntos para conseguir\(k+1\), tendrás una cadena más larga de primos multiplicada. Por lo tanto, (\(\forall i \leq k\)P (\(k\)))\(\Rightarrow\) P (\(k+1\)).

Por lo tanto, por la fuerte forma de inducción matemática,\(\forall n \geq 2\) P (\(n\)).

Puedes ver por qué necesitábamos la forma fuerte aquí. Si quisiéramos probar que 15 es expresable como producto de primos, saber que 14 es expresable como producto de primos no nos hace ni una pizca de bien. Lo que necesitábamos saber era que 5 y 3 eran expresables de esa manera. En general, la fuerte forma de inducción es útil cuando hay que romper algo en partes más pequeñas, pero no hay garantía de que las partes sean “una menos” que la original. Sólo sabes que serán más pequeños que los originales. A continuación se muestra un ejemplo similar.

Ejemplo 2

Anteriormente (p.) afirmamos que cada árbol libre tiene un borde menos que nodo. Demuéstralo.

Sea P (\(n\)) la proposición de que un árbol libre con\(n\) nodos tenga\(n-1\) bordes.

1. estuche base. P (1) es cierto, ya que un árbol libre con 1 nodo es solo un solo nodo solitario, y no tiene bordes.

2. paso inductivo. Ahora debemos probar que (\(\forall i \leq k\)P (\(k\)))\(\Rightarrow\) P (\(k+1\)). Dicho de otra manera, asumimos que todos los árboles más pequeños que el que estamos viendo tienen un nodo más que borde, y luego usamos esa suposición para demostrar que el árbol que estamos viendo también tiene un nodo más que borde.

   Procedemos de la siguiente manera. Toma cualquier árbol libre con\(k+1\) nodos. Quitar cualquier borde te da dos árboles libres, cada uno con\(k\) nodos o menos. (¿Por qué? Bueno, si eliminas algún borde de un árbol libre, los nodos ya no estarán conectados, ya que un árbol libre está “mínimamente conectado” como está. Y no podemos dividirlo en más de dos árboles eliminando un solo borde, ya que el borde conecta exactamente dos nodos y cada grupo de nodos del otro lado del borde eliminado todavía están conectados entre sí).

   Ahora la suma de los nodos en estos dos árboles más pequeños sigue siendo\(k+1\). (Esto se debe a que no hemos eliminado ningún nodo del árbol libre original, simplemente hemos eliminado un borde). Si dejamos\(k_1\) ser el número de nodos en el primer árbol, y\(k_2\) el número de nodos en el segundo, tenemos\(k_1 + k_2 = k + 1\).

   Bien, pero ¿cuántos bordes tiene el primer árbol? Respuesta:\(k_1 - 1\). ¿Cómo sabemos eso? Por la hipótesis inductiva. Estamos asumiendo que cualquier árbol más pequeño que\(k+1\) los nodos tiene un borde menos que el nodo, y así estamos aprovechando esa suposición (legal) aquí. De igual manera, el segundo árbol tiene\(k_2 - 1\) bordes.

   El número total de aristas en estos dos árboles es así\(k_1 - 1 + k_2 - 1\), o\(k_1 + k_2 - 2\). Recuerda eso\(k+1 = k_1 + k_2\) (no se eliminan los nodos), y así se trata de un total de\(k+1-2 = k-1\) aristas.

   Bingo. Quitar un borde de nuestro árbol original de\(k+1\) nodos nos dio un total de\(k-1\) bordes. Por lo tanto, ese árbol original debió haber tenido\(k\) bordes. Ahora hemos probado que un árbol de\(k+1\) nodos tiene\(k\) bordes, asumiendo que todos los árboles más pequeños también tienen un borde menos que un nodo.

Por lo tanto, por la fuerte forma de inducción matemática,\(\forall n \geq 1\) P (\(n\)).