Inducción Matemática

Anuncios

Principio de Inducción Matemática

La inducción para los matemáticos

La inducción matemática es un método de demostración que se utiliza cuando se trata de establecer la veracidad de una lista infinita de proposiciones.

El método es bastante natural para usarse en una variedad de situaciones en la ciencia de la computación.

Es decir, esta es (por favor no me maten matemáticos) su truco mejora guardado para demostrar proposiciones, esta es la oca de los huevos de oro.

También podemos ver a la inducción como una herramienta muy poderosa, una espada a máximo nivel, un arma en diamante en COD, tu y yo sabemos que el arma es poderosa, ahora te enseñare a usarla.

¿Cómo usamos la inducción?

Bueno, incluso podemos convertirlo en un «algoritmo», pero antes te comentaré que como todas las armas en los juegos no pueden estar tan OP (poderosas pues), así que te diré la debilidad de esta arma: SOLO FUNCIONA PARA LOS NÚMEROS NATURALES.

Una proposición $p(n)$ es verdadera para todos los valores de la variable $n$ si se cumplen las siguientes condiciones:

Paso 1 (Caso base): La proposición $p(n)$ es verdadera para $n = Natural$ .
Paso 2 (Hipótesis de Inducción): Se supone que $p(k)$ es verdadera , donde $k$ es un número natural cualquiera.
Paso 3 (Tesis de Inducción): Se demuestra que $p(k+1)$ es verdadera, es decir, $p(k) \implies p(k+1)$ .

Así se demuestra que la proposición $p(n)$ , para todo $n \in \mathbb{N}$ .

¿…Cómo?

Los 3 pasos de la inducción también se pueden escribir como:

Caso Base: Toma tu proposición, y encuentra un caso base, es decir el natural más pequeño que cumple la proposición.

Nota: Muchas, muchísimas veces es ese número es uno (ósea siempre se cumple), pero no siempre, así que no te confíes, encuentra ese caso base.

Supone que se cumple para k: Este es el paso más simple, lo único que tienes que hacer es creer (tratar como un axioma, como tu quieras verlo) que se cumple para el caso k.

Demuestra k+1: No todo en la vida podría ser tan fácil, este paso el el 95% de la dificultad del problema, usando lo del paso anterior tienes que demostrar que si se cumple para k A FUERZAS se cumple para K+1.

Si lograste llegar hasta aquí puedes decir con toda confianza que: DICHA PROPOSICIÓN ES VERDADERA (para todos los naturales : p) DESDE EL CASO BASE HASTA EL INFINITO.

¿Porqué funciona?

Podemos relacionar este poderoso principio con la analogía de las piezas de dominó: supongamos que tenemos una infinidad de piezas acomodadas, una detrás de la otra.

Ahora, si tiramos la primera, empujará a la segunda ocasionando que también caiga, esta a su vez empujará a la tercera y así sucesivamente, por lo que todas las piezas caerán.

El tirar la primer pieza es demostrar el caso base, y el demostrar si una pieza cae la siguiente también va a caer, es demostrar que $p(k) \implies p(k+1)$ .

Ejemplo #1

Problema. Demuestre que la suma de los primeros $n$ números naturales es $\dfrac{n(n+1)}{2}$ .

Solución. Vemos que la proposición que tenemos que demostrar es $\displaystyle \sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$ . Realizemos los tres pasos para demostrarla mediante inducción:

Paso 1: Para $n=1$ tenemos que $\displaystyle \sum_{i=1}^{1} i=1$ , y por otro lado $\dfrac{1(1+1)}{2}=1$ , por lo tanto la proposición es cierta para $n=1$ .
Paso 2: Supongamos que la proposición es verdadera para cualquier $k \in \mathbb{N}$ , es decir, supongamos que $\displaystyle \sum_{i=1}^{k} i = \dfrac{k(k+1)}{2}$ .
Paso 3: Probemos que la proposición es cierta para $k+1$ , es decir, probemos que $\displaystyle \sum_{i=1}^{k+1} i = \dfrac{(k+1)((k+1)+1)}{2}=\dfrac{(k+1)(k+2)}{2}$ . Al separar el último término de la suma tenemos que:

$\displaystyle \sum_{i=1}^{k+1} i=\sum_{i=1}^{k} i+(k+1)$

Pero por la hipótesis de inducción tenemos ahora:

$\displaystyle \sum_{i=1}^{k+1} i = \dfrac{k(k+1)}{2}+(k+1)$

Lo que resta es simple álgebra para llegar a la expresión deseada, factorizando y reacomodando tenemos que:

$\displaystyle \sum_{i=1}^{k+1} i = (k+1)\left(\dfrac{k}{2}+1\right)=\dfrac{(k+1)(k+2)}{2}$

Finalmente, por el principio de inducción matemática, se cumple que $\displaystyle \sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$ , para toda $n \in \mathbb{N}$ . $\quad \square$

Problema para el lector

Demuestre que la suma de los primeros $n$ números naturales impares es $n^2$ .

Ejemplo #2

Problema. Sea $F_1=F_2=1$ y $F_n=F_{n-1}+F_{n-2}$ para $n \geq 3$ . La sucesión anterior es conocida como la sucesión de Fibonacci. Demuestre que:

$F_n = \dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right)$ , para toda $n \in \mathbb{N}$ .

Sí, aunque no lo creas, hay una fórmula para calcular cualquier número de la sucesión de Fibonacci sin conocer los anteriores.

Solución. Usando inducción tenemos que:

Caso base: probemos que la proposición es cierta para $n=1$ y para $n=2$ . Por la definición tenemos que $F_1=F_2=1$ , y por la proposición tenemos que:

$F_1=\dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^1-\left(\dfrac{1-\sqrt{5}}{2}\right)^1\right)=\dfrac{1}{\sqrt{5}}\left(\dfrac{2\sqrt{5}}{2}\right)=1$

$F_2=\dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^2-\left(\dfrac{1-\sqrt{5}}{2}\right)^2\right)=\dfrac{1}{\sqrt{5}}\left(\dfrac{4\sqrt{5}}{4}\right)=1$

Por lo que la proposición es cierta para $n=1$ y $n=2$ .

Hipótesis de inducción: supongamos que la proposición se cumple para $n \geq 3$ , es decir, supongamos que $F_n = \dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right)$ .
Tesis de inducción: probemos que la proposición es cierta para $n+1$ , es decir, probemos que $F_{n+1} = \dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+1}\right)$ . Al usar la definición de la sucesión tenemos que $F_{n+1}=F_n+F_{n-1}$ , pero por la hipótesis de inducción eso es:

$F_{n+1}=\dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right)+\dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\dfrac{1-\sqrt{5}}{2}\right)^{n-1}\right)$

Factoricemos un poco para que se vea más sencilla la expresión:

$F_{n+1}=\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^n\left(1+\left(\dfrac{1+\sqrt{5}}{2}\right)^{-1}\right)-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\left(1+\left(\dfrac{1-\sqrt{5}}{2}\right)^{-1}\right)\right]$

Pero $1+\left(\dfrac{1+\sqrt{5}}{2}\right)^{-1}=\dfrac{1+\sqrt{5}}{2}$ , y $1+\left(\dfrac{1-\sqrt{5}}{2}\right)^{-1}=\dfrac{1-\sqrt{5}}{2}$ , por lo tanto:

$F_{n+1}=\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^n\left(\dfrac{1+\sqrt{5}}{2}\right)-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\left(\dfrac{1-\sqrt{5}}{2}\right)\right]$

$F_{n+1}=\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+1}\right]$

Que es justo lo que queríamos demostrar, así, por inducción matemática, nuestra proposición es cierta para toda $n \in \mathbb{N}$ . $\quad \square$

Ejemplo #3

En ocasiones necesitamos aplicar la inducción matemática para demostrar alguna proposición que parece cierta para valores pequeños de $n$ , veamos cómo con el siguiente problema.

Problema. Sea $f : \mathbb{N} \to \mathbb{Q}$ tal que:

$f(1)=2017$
$\displaystyle \sum_{i=1}^{n} f(i)=n^2f(n)$ para $n \geq 2$

Halla el valor de $f(2017)$ .

Solución. Usemos de nuevo el truco de sacar el último término de la suma de la siguiente forma:

$\displaystyle \sum_{i=1}^{n-1} f(i)+f(n)=n^2f(n)$

Pero aguarda, el valor de $\displaystyle \sum_{i=1}^{n-1} f(i)$ es justamente $(n-1)^2f(n-1)$ por la definición de $f$ . Entonces tenemos:

$(n-1)^2f(n-1)+f(n)=n^2f(n)$

Ahora despejemos $f(n)$ en términos de $f(n-1)$ :

$f(n)=\dfrac{(n-1)^2f(n-1)}{n^2-1}=\dfrac{(n-1)^2f(n-1)}{(n+1)(n-1)}$

Podemos cancelar con toda seguridad el factor $(n-1)$ ya que recordemos que esta definición es para $n \geq 2$ , entonces:

$f(n)=\dfrac{n-1}{n+1}f(n-1)$

Hasta este punto tenemos una definición recursiva de $f$ , de tal forma que para calcular $f(n)$ solo necesitamos conocer $f(n-1)$ , calculemos algunos valores:

$f(2)=\dfrac{2-1}{2+1}f(2-1)=\dfrac{1}{3}f(1)$

$f(3)=\dfrac{3-1}{3+1}f(3-1)=\dfrac{2}{4}f(2)=\dfrac{1}{2} \cdot \dfrac{1}{3} f(1)=\dfrac{1}{6}f(1)$

$f(4)=\dfrac{4-1}{4+1}f(4-1)=\dfrac{3}{5}f(3)=\dfrac{3}{5} \cdot \dfrac{1}{6} f(1)=\dfrac{1}{10}f(1)$

$f(5)=\dfrac{5-1}{5+1}f(5-1)=\dfrac{4}{6}f(4)=\dfrac{2}{3} \cdot \dfrac{1}{10} f(1)=\dfrac{1}{15}f(1)$

Parece que la fórmula de $f$ es $f(n)=\dfrac{2}{n(n+1)}f(1)$ , demostrémoslo por inducción:

Caso base: Para $n=1$ tenemos que $f(1)=\dfrac{2}{1(1+1)}f(1)=f(1)$ , por lo que la fórmula es cierta para $n=1$ .
Hipótesis de inducción: Supongamos que $f(n)=\dfrac{2}{n(n+1)}f(1)$ .
Tesis de inducción. Probemos que $f(n+1)=\dfrac{2}{(n+1)((n+1)+1)}f(1)=\dfrac{2}{(n+1)(n+2)}f(1)$ . Por la definición recursiva tenemos que:

$f(n+1)=\dfrac{(n+1)-1}{(n+1)+1}f((n+1)-1)$

$f(n+1)=\dfrac{n}{n+2}f(n)$

Pero por la hipótesis de inducción:

$f(n+1)=\dfrac{n}{n+2} \cdot \dfrac{2}{n(n+1)}f(1)$

$f(n+1)=\dfrac{2}{(n+1)(n+2)}f(1)$

Por lo que tenemos que $f(n)=\dfrac{2}{n(n+1)}f(1)$ para todo $n \in \mathbb{N}$ . Finalmente, podemos decir con toda seguridad que $f(2017)=\dfrac{2}{2017(2017+1)}f(1)=\dfrac{2}{2017(2018)}(2017)=\dfrac{1}{1009}$ . $\quad \square$