En esta entrada continuaremos con ejemplos de uso del principio de inducción en la resolución de problemas. Es una continuación de la entrada anterior. Como recordatorio, aquí está el principio de inducción en la forma en la que lo hemos estado usando:
Principio de inducción. Sea una afirmación (o proposición o propiedad) que depende del número natural
. Si
- la afirmación
es cierta y
- la veracidad de la afirmación
implica la veracidad de la afirmación
,
entonces la afirmación es cierta para toda
.
Lo que nos interesa ahora es ver cómo el principio de inducción se mezcla con algunas de las heurísticas de resolución de problemas.
Inducción y trabajar hacia atrás
Lo que hemos hecho hasta ahora es lo siguiente. Tomamos un enunciado que depende de un entero . Comenzamos probándolo para la base inductiva. Luego, suponemos la veracidad del enunciado para cierto entero
. A partir de ahí, intentamos conseguir la veracidad del enunciado para el entero
.
Como vimos cuando platicamos de trabajar hacia atrás, eso no siempre es lo más natural en la resolución de un problema. En algunas ocasiones nos conviene más empezar con el enunciado que queremos demostrar y mostrar que mediante pasos reversibles podemos llegar a algo cierto. Queremos aplicar esta idea para la demostración del paso inductivo.
Consideremos el siguiente ejemplo.
Problema. Demuestra que para todo entero no negativo se tiene que
Solución. Tenemos que probar la afirmación para entero. Procedemos por inducción sobre
. Si
, la expresión es igual a
, así que la afirmación es cierta. Supongamos entonces que
Nuestro objetivo es mostrar que esta expresión es entera. Nos gustaría usar la hipótesis inductiva, así que queremos intentar encontrar dentro de esta expresión la expresión para . Esto lo podemos hacer usando el binomio de Newton para abrir los binomios a potencias y luego agrupando. Tenemos que
Así, cuando hagamos la suma tenemos los términos


Si no comenzábamos a manipular la expresión para , hubiera sido muy difícil, sólo a partir de la de
, llegar a la de
.
Inducción y generalización
Una forma sencilla de combinar inducción con generalización es la siguiente:
- Nos piden demostrar una afirmación para un natural muy específico.
- En vez de eso, construimos un problema más general que funcione «para todos los naturales».
- Resolvermos ese problema por inducción.
Veamos un ejemplo.
Problema. Muestra que
Solución. Sean y
. Se pide mostrar que
es un entero impar. Mostraremos que, de hecho,
es un entero impar para todo entero
. Vamos a proceder por inducción fuerte (hablaremos un poco más de eso más adelante).
El primer caso es y notemos que
Notemos también que
, de modo que
, que también es impar. Supongamos ahora que sabemos que la afirmación es cierta para exponentes
y
.
Consideremos el polinomio cuadrático







De aquí la conclusión inductiva es inmediata. Como la hipótesis inductiva es que el resultado es cierto para los exponentes y
, entonces en el lado derecho tenemos una suma de un entero impar con un entero par, que es un entero impar. Esto muestra que la afirmación es cierta para cuando los exponentes son
.
Para demostrar el problema original, basta con hacer la observación de que, en particular, es un entero impar.
Hay otra forma de combinar inducción con generalización, pero es un poco más sofisticada. Para explicarla, es mejor comenzar con un ejemplo.
Problema. Demuestra que para todo entero se tiene que
Antes de resolver el problema, intentemos hacer una solución «ingenua» que quiera usar inducción de manera directa. No hay ningún problema con hacer la base de inducción, pues para al lado izquierdo tenemos únicamente
y al lado derecho
. Supongamos que el resultado es cierto para
, es decir, que
Llamémosle a la expresión del lado izquierdo. Lo que queremos probar ahora es que el resultado es cierto para
, es decir, que
. Sabemos que
, pero ahora estamos sumando un término positivo adicional. Es posible que este término arruine la desigualdad, pues
es una afirmación «muy débil». Veamos cómo darle la vuelta a esta dificultad.
Solución. Sea la afirmación del problema. Consideremos la afirmación
que dice que para todo entero
se tiene que
Si logramos demostrar , entonces
será cierta de manera inmediata, pues
. Vamos a demostrar
por inducción.
Tenemos que es cierto pues en ambos lados de la igualdad queda
. Supongamos que
es cierto. Usando esto, tenemos que
es decir, que es cierto. Así, por inducción
es cierto para todo entero
y con eso
también.
Lo que sucedió fue lo siguiente. Al hacer el paso inductivo, intentamos mostrar que implica
. Pero esto es imposible pues
«es muy débil», o bien «pierde información de todo lo que está pasando». Sin embargo, cuando consideramos la afirmación auxiliar
, resulta que esta «tiene más información». Aquí, esta información es «qué tal lejos está la expresión de
«
La afirmación tiene tanta información, que ahora sí con ella se puede probar
. Se termina el problema usando que
implica
. Así, la estrategia fue la siguiente:
- Se tiene una afirmación
que se quiere demostrar para todos los naturales. Hacer inducción no parece funcionar, pues
parece no ser suficiente para probar
- Se considera entonces una afirmación
más fuerte (que implique a
), pero para la cual
sí pueda probar
.
- Se prueba
por inducción, y se concluye que
es cierta.
Hay que ser cuidadosos. Parte del ingenio en usar esta estrategia consiste en poder identificar un balance la generalización que necesitamos de modo que sí sirva para solucionar el problema original, pero que no sea demasiado ambiciosa como para que sea falsa.
Más ejemplos
Hay más ejemplos bastante elaborados del uso de estas ideas en Problem Solving Through Problems de Loren Larson, Secciones 2.1, 2.2, 2.3 y 2.4. Otro libro con muchos ejemplos interesantes es el Putnam and Beyond, de Gelca y Andreescu. También hay otros ejemplos de inducción en las siguientes entradas: