Source: http://blog.nekomath.com/seminario-de-resolucion-de-problemas-principio-de-induccion-parte-2/
Timestamp: 2020-07-16 02:56:30+00:00

Document:
Seminario de Resolución de Problemas: Principio de Inducción, Parte 2 - El blog de Leo
Seminario de Resolución de Problemas: Principio de Inducción, Parte 2
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.
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
es entero y consideremos la expresión
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
cuya suma es entera por hipótesis inductiva,
que es entero pues es entero y , de modo que la suma total es suma de enteros y por lo tanto es un entero. Esto termina la prueba por inducción.
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.
Problema. Muestra que
es un entero impar.
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
Como y son raíces, tenemos que y . Multiplicando estas igualdades por y respectivamente, sumando ambas igualdades obtenidas, y despejando llegamos a
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.
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:
El lema del intercambio de Steinitz
Principio de Inducción, Parte 1
Principio de Inducción, Parte 3
Esta entrada se publicó en Matemáticas y está etiquetada con desigualdad, enteros, generalizar, heurísticas, inducción, naturales, trabajar hacia atras en marzo 23, 2020 por Leo.
← Álgebra Lineal I: Forma matricial de una transformación lineal Seminario de Resolución de Problemas: Principio de Inducción, Parte 3 →

References: Resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 Resolución