Source: http://blog.nekomath.com/seminario-de-resolucion-de-problemas-principio-de-induccion/
Timestamp: 2020-03-30 13:09:36+00:00

Document:
Seminario de Resolución de Problemas: Principio de Inducción - El blog de Leo
Seminario de Resolución de Problemas: Principio de Inducción
El principio de inducción es una de las piedras angulares de las matemáticas y de la resolución de problemas. Es altamente probable que ya lo hayas utilizado previamente, en cursos como Álgebra Superior I y II, en Álgebra Lineal, en Cálculo y varios otros.
En esta entrada y las siguientes repasaremos la idea general del principio de inducción, pero además veremos lo flexible que puede ser en la resolución de problemas.
La idea general que debes tener cuando hagas inducción es pensar en Tlaloc (dios de la lluvia). Imagina que Tlaloc decide que llueva hoy, y además decide que si llueve un día, entonces lloverá también al día siguiente. Como llueve hoy, entonces lloverá mañana, pero como llueve mañana entonces lloverá pasado mañana. De hecho, ¡va a llover todos los días a partir de hoy!
De manera general, el principio de inducción sirve para cuando se quieren probar afirmaciones «para todo número natural » y en donde para probar la afirmación para un valor es útil tener la validez de la afirmación para los valores anteriores. Sin embargo, se puede también utilizar para probar afirmaciones «a partir de cierto natural». Enunciamos esta versión a continuación.
En estos términos, a probar la afirmación para se le conoce como probar la base de inducción. Suponer la veracidad de para una se conoce como suponer la hipótesis inductiva, y a probar la veracidad de se le conoce como hacer el paso inductivo. Así, para hacer una prueba por inducción se tienen que hacer los siguientes pasos:
Probar la base de inducción, osea, mostrar que es válido.
Suponer, libremente, la hipótesis inductiva, es decir, suponer que cierto.
A partir de la hipótesis inductiva, y el resto de las hipótesis del problema, hacer el paso inductivo, es decir, demostrar .
Es muy importante hacer estos tres pasos. Si no se prueba la base de inducción, es como si Tlaloc no decidiera que lloviera hoy: no hay forma de saber qué pasara. Si no se hace el paso inductivo, es como si Tlaloc no dijera nada de la lluvia de un día a partir del anterior.
La creatividad en el uso de la inducción en la resolución de problemas reside en varios aspectos. A veces:
Se requiere ingenio para probar el caso base.
Se requiere ingenio para saber exactamente cómo usar la hipótesis inductiva para hacer el paso inductivo.
Se requiere crear una afirmación auxiliar más fuerte que implique a , tal qué sí se pueda probar por inducción, pero no, de lo cual veremos ejemplos en siguientes entradas.
Veamos algunos ejemplos de problemas que se pueden resolver utilizando induccicón. En el primer problema vamos a ser muy explícitos en cómo estamos ejecutando la inducción. Esto te puede ayudar cuando estas haciendo tus primeras pruebas de inducción: te ayudará a ser explícito en demostrar la base, en suponer la hipótesis inductiva y en hacer el paso inductivo.
En algunas otras de las demostraciones, vamos a ser un poco más flexibles con cómo se escribe la demostración. No hay que ser totalmente explícitos en qué parte de demostración por inducción se está haciendo. Esto te puede ayudar para cuando ya estas escribiendo una prueba más larga y la parte inductiva sólo es un pequeño fragmento del argumento.
Problema. Sea un número entero y números reales. Considera todas las expresiones que puedes hacer de la forma
donde cada es o . Demuestra que al pasar por todas las posibilidades para las se forman por lo menos números diferentes.
Solución. Vamos a proceder por inducción sobre . Hagamos primero la base de inducción. Como queremos demostrar la afirmación para toda , el caso base es . Cuando , tenemos un sólo número real y lo que tenemos que demostrar es que hay al menos valor en las expresiones que se pueden formar. Si o , obtenemos las expresiones y respectivamente, que son al menos dos. Esto prueba el caso base.
Ahora supongamos la hipótesis inductiva. Es decir, suponemos libremente que para cierta , cada que tomamos números reales se cumple la afirmación del problema, es decir, que al pasar por las posibilidades de , se obtienen al menos expresiones diferentes.
La parte final es hacer el paso inductivo. Es decir, a partir de todas las hipótesis del problema, de la hipótesis inductiva, y de otras ideas, tenemos que probar la afirmación para . Así, tomemos números reales
Tenemos que mostrar que usando coeficientes y podemos formar al menos números distintos.
Una buena idea es aprovechar que ya sabemos que los números
ya hacen varias expresiones. Podemos aplicar la hipótesis inductiva a estos números, y con ello logramos conseguir al menos expresiones diferentes. Notemos que estas expresiones también sirven para cuando tenemos a y le ponemos coeficiente . Lo que tenemos que hacer ahora es conseguir expresiones nuevas.
Consideremos la expresión en la que todos los coeficientes son . Esta es claramente mayor que cualquiera de las otras que ya tenemos. Además, todas las expresiones , , , , son mayores que (pues es el más grande de los ‘s), son todas diferentes, y son de la forma deseada (pues cada con está en ).
De esta forma, conseguimos expresiones distintas y todas ellas mayores que , así que distintas de todas las dadas por la hipótesis inductiva. Con esto completamos la demostración.
La inducción sirve para probar afirmaciones que dependen de un número natural. Sin embargo, no siempre es inmediato de dónde sale este natural. A veces ese natural aparece simplemente como el tamaño de algún conjunto involucrado. A veces hay que hacer una demostración para «todos los polinomios» y entonces podríamos intentar hacer inducción sobre el grado del polinomio. En otro problema puede que se tenga que mostrar algo «para todas las matrices» y entonces tal vez tengamos que demostrarlo por inducción sobre las dimensiones de la matriz.
Problema. Se dibuja una cantidad finita de lineas en el espacio de modo que no haya tres de ellas que pasan por un mismo punto. Estas líneas definen regiones en el plano. Muestra que se pueden colorear estas regiones de blanco o negro de modo que no haya dos regiones del mismo color que tengan un lado en común.
El problema no tiene ningún número natural explícitamente en el enunciado. Sin embargo, se pide demostrar algo para una cantidad finita de cosas, así que basta probar la afirmación para cosas, para todo entero . De esta forma, la variable «cantidad de líneas que tenemos» ya es una variable sobre la cual podemos hacer inducción. Hagamos la demostración así.
Solución. Procedamos por inducción sobre el número de líneas. Si tenemos líneas, sólo hay una región en el plano. La pintamos de blanco.
Ahora, supongamos que cada que tenemos líneas, no tres de ellas por un punto, podemos hacer una coloración de su conjunto de regiones de modo que no haya dos adyacentes del mismo color.
Tomemos cualquier conjunto de líneas. Tomemos una de ellas e ignorémosla por el momento. Por hipótesis inductiva, podemos hacer una coloración para las líneas que quedan. Al regresar se hacen nuevas regiones. A las regiones que quedan de un lado de , las dejamos del color que ya tenían. A las que están del otro lado de , les intercambiamos el color (blanco a negro y viceversa).
El nuevo acomodo funciona pues todas las regiones de totalmente contenidas en alguno de los lados de siguen sin problemas. Y aquellas regiones de cortadas por sólo pueden tener problemas con un lado que caiga sobre . Pero de estos problemas tampoco hay pues de un lado quedaron de un color, y del otro del otro.
Observa que en el problema anterior ya no estamos haciendo los pasos de la inducción tan «explícitos».
A veces hay problemas en los que hay una variable entera, pero no necesariamente hay que aplicar inducción para esa variable, sino para otro parámetro que introduzcamos.
Problema. Dado un entero positivo y un real , muestra que
Recuerda que es el mayor entero que sea menor o igual a .
Solución. El problema con hacer inducción en es que no hay una forma sencilla de relacionar el resultado para y el resultado para . Tampoco podemos hacer «inducción sobre » porque es un número real.
El truco para el problema es probar el resultado para todas las en el intervalo para todo entero . Con esos intervalos cubrimos a todos los reales positivos, y por lo tanto cubrimos todas las posibilidades para . Para probar que se vale en esos intervalos, vamos a proceder por inducción sobre .
Si , entonces queremos mostrar el resultado para el intervalo . Para las en este intervalo, cada uno de los términos (para ) es menor que y por lo tanto el lado izquierdo de la igualdad que queremos mostrar tiene puros sumandos y entonces es igual a . También para las en este intervalo tenemos , y así el lado derecho también es . Esto prueba la base inductiva.
Supongamos ahora que el resultado es cierto para en el intervalo para cierto entero . Esto quiere decir que
Tomemos ahora un entero en el intervalo . Notemos que está en el intervalo anterior, de modo que cumple la igualdad de la hipótesis inductiva. Notemos además que si en
substituimos , obtenemos
El último sumando es , de modo que en el lado izquierdo tenemos todos los sumandos del lado izquierdo de la hipótesis inductiva y un . Así, el lado izquierdo es igual a
Puedes encontrar más ejemplos en la Sección 2.1 del Problem Solving through Problems de Loren Larson. Otro libro con muchos ejemplos interesantes es el Putnam and Beyond, de Gelca y Andreescu. Así mismo, aquí en el blog hay otras entradas en las que se hacen pruebas por inducción.
Principio de inducción, Parte 2
Esta entrada se publicó en Matemáticas y está etiquetada con coloración, combinación lineal, inducción, lineas, parte entera en marzo 18, 2020 por Leo.
← Seminario de Resolución de Problemas: Principio de las Casillas Álgebra Superior II: Problemas de divisibilidad →

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