Principio de Inducción Finita
¡Bienvenido, espero que estés bien!
Vamos a comenzar la clase con la siguiente situación: imagina que estás en una fila para comprar pan, al igual que tú muchas personas están formadas, son tantas que ni siquiera podrías contarlas, esa cantidad de personas será llamada \(n\).
Bien, estás ahí esperando tú pan y, de la nada, aparece un empleado y empieza a repartir jamón desde la primera persona en la fila.
Te pones feliz, ¿verdad? “¡Además de pan, tendré jamón!”
Felicidades, acabas de utilizar el razonamiento inductivo. Esta vez aprenderemos sobre el Principio de Inducción Finita (PIF), que es justamente la herramienta matemática para PROBAR ese tipo de razonamientos. Genial, ¿no?
“¡¿Que?! Yo no hice nada. Solo pensé que al igual que todos, a mi también me darían jamón gratis”
Pero ese es un razonamiento inductivo.
“¿Para qué sirve el PIF?”
Lo que ocurre, es que en varias Ciencias aparecían situaciones que parecían seguir un patrón. Pero el problema era el siguiente: los estudiosos podían probar todos los números que quisieran, pero nunca serían suficientes para probar que el patrón existía.
Por ejemplo: Ya debes haber visto cómo es la suma de \(n\) términos de una P.A de razón \(1\):
\[1+2+3+\ldots+n=\frac{n(n+1)}{2}\]
Todo bien, sabemos que esa igualdad es verdadera, PERO matemáticamente tendríamos que probarla. Es decir, puede que esa operación funcione con 10000 pero no con 10001 (seamos honestos, nadie tiene la paciencia de llegar hasta ese número), ¿entiendes? Por eso, usamos el PIF, para probar que eso es cierto.
Los sabios sabían que para responder las preguntas de los problemas, no bastaba con “probar” si las fórmulas eran verdaderas solo sustituyendo valores específicos para \(n\). No importa cuántos valores hubieran probado, podría haber alguno que pasaran por alto. Existe una brecha cuando se habla de algo “probablemente verdadero” y “absolutamente cierto”.
Bien, basta de bla-bla-bla, vamos al grano.
Principio de Inducción Finita (1a versión)
En este caso tenemos dos condiciones que deben ser satisfechas. Probarlas nos garantiza la validez de la proposición para la infinidad de términos que existen.
Ejemplo:
\[\text {Utilice el PIF } 1 \text { para mostrar que } 1+2+3+\ldots+n=\frac{n(n+1)}{2}\]
¡Bien, veamos el paso a paso para resolver este tipo de preguntas!
Paso 1:
El primer paso SIEMPRE es saber quien es \(P(n)\), en este caso
\[P(n)=\frac{n(n+1)}{2}\]
Es decir, lo que queremos probar es que aquella suma siempre es igual a \(\frac{n(n+1)}{2}\)
Paso 2:
El segundo paso es comenzar a atacar las dos condiciones, iniciando por la primera.
Lo que hacemos aquí es conseguir un número \(n_{0}\) tal que \(P\left(n_{0}\right)\) sea verdadera. Ese será el caso base, ¿sabias? Aquel que te resguarda en el caso más básico.
\[n_{0}=1\]
Ahora, tenemos que verificar cual es la suma de \(1\) término en la P.A de razón \(1\). Es el propio \(1\), ¿de acuerdo? Y luego de encontrar ese valor, calculamos \(P(1)\):
\[P(1)=\frac{1(1+1)}{2}=1\]
Entonces \(P(1)\) es verdadera.
Paso 3:
Todos los pasos son importantes, pero este específicamente, es MEGA importante y requiere toda tu atención.
¡Vamos a utilizar la HIPÓTESIS INDUCTIVA!
“¿Ah? ¿Qué es eso?”
La hipótesis inductiva no es más que utilizar la segunda condición del PIF. Vamos a asumir que esa relación \(P(n)\) es válida para algún \(k\) que sea mayor que \(n_{0}=1\), entonces intentaremos probar que \(P(k+1)\) es verdadera.
Entonces, estamos usando la HI (hipótesis inductiva o de inducción), diciendo que:
\[P(k)=\frac{k(k+1)}{2}\]
Y queremos probar que \(P(k+1)\) es verdadera. Échale un vistazo a donde queremos llegar:
\[P(k+1)=\frac{(k+1)(k+2)}{2}\]
¿Cómo hacemos eso? Mira:
\[1+2+3+\ldots+n=\frac{n(n+1)}{2}\]
Sabemos que esa relación es válida para \(k\), entonces:
\[1+2+3+\ldots+k=\frac{k(k+1)}{2}\]
Queremos llegar a \(k+1\), entonces sumamos \(k+1\) en los dos lados:
\[1+2+3+\ldots+k+(k+1)=\frac{k(k+1)}{2}+(k+1)\]
Como puedes ver, NO SUSTITUIMOS, sino que sumamos. En el lado izquierdo no tenemos que hacer, ya que tiene lo que necesitamos, que es la suma hasta \((k+1)\), vamos a utilizar el lado derecho:
\[1+2+3+\ldots+k+(k+1)=\frac{k(k+1)+2(k+1)}{2}\]
\[1+2+3+\ldots+k+(k+1)=\frac{(k+1)(k+2)}{2}\]
Genial, llegamos a donde queríamos, \(P(k+1)\) es verdadera. Entonces, por el Principio de Inducción Finita versión \(1\) (o también llamado Principio de Inducción Débil), \(P(n)\) es verdadera.
∎
No te asustes, este paso no suele ser tan largo, pero quería hacerlo bien para que entiendas.
Principio de Inducción Finita (2da versión)
Este PIF luce como el otro, pero tiene una aplicación diferente y mucho más fuerte, tanto que es llamado “Principio de Inducción Finita versión 2” o “Principio de Inducción Fuerte”.
Mira el ejemplo:
\[\text {Demuestre que todo natural es un número primo o es un producto de primos.}\]
Paso 1:
\[P(n)=n \text { es primo o producto de primos}\]
“Ah, eso no es verdad para el número \(1\)”
Bien, entonces utilizaremos el número \(2\). Lo importante en el caso base, es que esta funcione para todos los otros casos mayores que sí mismo. Entonces probaremos si esa proposición verdadera para todo \(n>1\).
\[P(n)=n \text { es primo o producto de primos, } n>1\]
Listo, identificamos la proposición, es decir, lo que queremos probar.
Paso 2:
El primer paso de las dos versiones es igual, o sea, necesitamos un caso base que sea verdadero.
\[2 \text { es primo, entonces } P(2) \text { es verdadera.}\]
Tenemos un caso base.
Paso 3:
Es hora de usar la HIPÓTESIS INDUCTIVA, vamos a aplicar la segunda condición.
Si intentamos usar el PIF 1, no llegaremos a ningún sitio, usando que \(P(k)\) es verdadera:
\[k \text { es primo o producto de primos}\]
¿Y ahora? ¿Cómo hacemos para probar que \(k+1\) también obedece a eso? Es mucho más complicado. Entonces, usaremos el PIF 2 para facilitar el proceso.
Usaremos la hipótesis inductiva, afirmando que:
\[n_{0} \leq k<n\]
\[2 \leq k<n\]
Para toda \(k\) en ese intervalo, \(P(k)\) es verdadera. Recordando que tiene que ser verdad, en realidad estamos afirmando que:
\[P(2) \wedge P(3) \wedge P(4) \wedge P(5) \wedge \ldots \wedge P(n-1) \text { es verdadera }\]
Entonces lo que nos queda por probar es si \(P(n)\) es verdadera.
Para el caso \(n\), tenemos dos posibilidades: o es primo o no lo es. Si es primo, entonces \(P(n)\) es verdadera. Pero si no lo es, se puede escribir de la siguiente manera:
\[n=p \cdot k\]
Donde esa \(p\) es un primo que divide \(n\), debido a que si \(n\) no es primo, tiene que ser divisible por algún primo.
Tenemos que tener en mente lo siguiente: \(n \neq p,\) entonces \(k>1\).
Además, \(p>1\), ya que es primo, entonces \(k<n\).
Por lo tanto, teniendo estos dos argumentos, podemos usar la hipótesis inductiva afirmando que: \(k \text { es primo o producto de primos.}\) (Afirmamos que eso es verdad para todo \(2 \leq k<n\))
Entonces, \(n\) está siendo escrito como un producto de primos, es decir, \(P(n)\) es verdadera por el PIF 2 y la propiedad \(P\) es válida para cualquier \(n>1\).
∎
¡Vamos a los ejercicios!
Hay un error?
Ir al Siguiente Capitulo: Introducción a los Conjuntos
Todos los Resúmenes
