Inducción Matemática

fuentes2

Principio de Inducción Matemática

oca

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.

arma.png

¿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?

dominoPodemos 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


Ahora estas listo mi joven padawan, ve y usa sabiamente esta poderosa arma. Suerte y que la fuerza te acompañe.

padawan

btn1 btn
btn

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s