La Inducción Matemática

En matemáticas hay varias formas de demostrar resultados. Entre ellas se  encuentran la demostración por reducción al absurdo, que consiste en suponer lo contrario a lo que quieres demostrar y llegar a una contradicción; la demostración por el contrapositivo, que se utiliza cuando el objetivo es demostrar una implicación, $p \Longrightarrow q,$ y consiste en demostrar $\neg q \Longrightarrow \neg p,$ que es equivalente; la demostración directa, que consiste en llegar a demostrar lo que quieres partiendo directamente de las hipótesis; etc. Un caso particular es cuando queremos demostrar una afirmación sobre todos los números naturales (o relacionada con ellos) a partir de uno en particular. En este caso se puede intentar utilizar la inducción, que nos permite demostrar dicha afirmación si conseguimos comprobar un par de condiciones:
  1. Para cierto $n_1 \in \mathbb{N}$ la afirmación es cierta.
  2. Si la afirmación es cierta para $n$ entonces lo es también para $n+1.$
La primera condición se conoce como caso base y la segunda como hipótesis de inducción (porque para demostrarlo se asume que la afirmación es cierta para $n$). La forma intuitiva de interpretar esto es imaginar una cadena infinita de fichas de dominó puestas verticalmente y seguidas. Si conseguimos ver que están suficientemente cerca cada una de la siguiente y decidimos tirar una de ellas (hacia el lado con infinitas fichas) entonces todas las demás caerán también. La condición primera sería tirar la primera ficha y la segunda condición sería ver que el resto están cerca cada una de la siguiente.
Si lo pensamos de otra forma más directa: estamos viendo que $n_1 \in \mathbb{N}$ cumple cierta propiedad ($n_1$ es un número natural en particular). Además también vemos que si un número la cumple entonces el siguiente también la cumplirá. Por tanto, como $n_1$ la cumple, la cumplirá $n_1 +1$ y por tanto también la cumplirá $n_1 +1 +1 =n_1 +2$ y así todo el rato, luego habremos demostrado que a partir de $n_1$ todos los naturales la cumplirán.

Hay una "versión fuerte" (llamada así porque se utiliza una hipótesis algo más fuerte) de la inducción que esencialmente dice lo mismo que la inducción, pero cambia la segunda condición:
  1. Para cierto $n_1 \in \mathbb{N}$ la afirmación es cierta.
  2. Si la afirmación es cierta para todo $k$ con $n_1\leq k \leq n$ entonces lo es también para $n+1.$
La diferencia es que en este caso estamos utilizando unas hipótesis que quizá resulten más cómodas, ya que podemos asumir que la afirmación no sólo se cumple para $n,$ sino que también se cumple para todos los números anteriores a $n.$  Esta versión es equivalente a la inducción habitual:

Para demostrar una equivalencia (o doble implicación $\Longleftrightarrow$) en matemáticas es necesario demostrar ambas implicaciones ($\Longleftarrow$ y $\Longrightarrow$). Lo que vamos a demostrar es que si tenemos una afirmación, dada una prueba por inducción (PI), se puede construir otra por inducción fuerte (PIF), y el recíproco: dada una prueba por inducción fuerte, se puede tener una prueba por inducción: $$\text{PI }\Longleftrightarrow \text{ PIF.}$$ $ \Longrightarrow)$ Supongamos que tenemos una prueba por inducción de una propiedad, $\xi $, y $\varphi(n)$ es la afirmación "si $\xi(n)$ es cierta para $n$ entonces es cierta para $n+1$" es cierta (es la prueba por inducción). El caso base para la inducción fuerte sigue siendo el mismo. Por otro lado, si $\psi(n)$ es la afirmación "si $\xi(k)$ es cierta para todo $n_1\leq k \leq n$ entonces lo es para todo $n_1\leq k \leq n+1$", $\psi(n)$ sería cierta para todo $n_1\leq n$ al serlo $\varphi(k)$ para todo $n_1\leq k$ y sería una prueba por inducción fuerte en la que no es necesario utilizar los casos $n_1\leq k\leq n.$

$\Longleftarrow )$ Ahora supongamos que tenemos una prueba por inducción fuerte de $\xi(n)$, con la misma notación que antes: el caso base es el mismo. Si tenemos $\psi(n)$ para todo $n$ entonces $\xi(n)$ es cierta para todo $n.$ De hecho, el recíproco también es cierto: si $\xi(n)$ es cierta para todo $n$ entonces tenemos $\psi(n)$ para todo $n,$ y por tanto la prueba se convierte en otra prueba de $\psi(n)$ por inducción.


Otra observación fácil que podemos hacer es que una prueba por inducción en $m$ con caso base $m_1$ es equivalente también a otra con caso base $1$ en $n$ para $n=1+m_1-m,$ luego toda prueba por inducción se puede transformar en otra igual pero para $n_1=1.$

La inducción es una herramienta muy útil y potente, que permite a los matemáticos demostrar resultados muy variados. Si bien algunos de los ejemplos que veremos a continuación son fáciles y simples, la inducción se puede utilizar también para probar grandes teoremas del álgebra, de la teoría de Galois, de la teoría de la medida o de teoría de números (entre otros muchos). Lo que sigue a continuación son unos ejemplos fáciles de cómo aplicar la inducción.

Vamos a demostrar que la suma de los primeros $n$ números naturales es $\frac{n(n+1)}{2}:$

1. El caso base $n=1:$ la suma es $1.$
2. Supongamos que $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}:$ $$\sum_{i=1}^{n} i =n+1 + \sum_{i=1}^{n} i $$y aplicando la hipótesis de inducción:$$=\frac{n(n+1)}{2}+n+1= \frac{(n+1)(n+2)}{2}$$que es precisamente lo que buscábamos.


Vamos a demostrar que dado un conjunto finito $A$ con $|A|=n,$ el conjunto de sus partes tiene cardinal $2^n.$ Lo primero es ver que da igual el conjunto que cojamos. Si es finito, tiene una biyección con un subconjunto de los naturales acotado. Si $|A|=n$ hay una biyección con $I_n=\left\lbrace 1,2,3,\ ..., n \right\rbrace$ y por tanto da igual qué conjunto cojamos, que sus partes van a tener tantos elementos como tiene las partes de $I_n.$ Ahora vamos con la inducción:

1. Si $n=|A|=1$ entonces $\mathcal{P}(A)=\left\lbrace \emptyset, A \right\rbrace$ y tiene $2\ (=2^1)$ elementos.
2. Supongamos que $|A|=n$ y $\left|\mathcal{P}(A)\right|=2^n.$ Queremos ver que si $a \notin A$ entonces $|A\cup \left\lbrace a \right\rbrace|=n+1$ y $\left|\mathcal{P}(A\cup \left\lbrace a \right\rbrace)\right|=2^{(n+1)}.$ Lo primero es ver que $A\cup \left\lbrace a \right\rbrace$ está en biyección con $I_{n+1},$ puesto que $a \notin A$ y por tanto tiene cardinal $n+1.$ El problema se traduce ahora en ver que $\left|\mathcal{P}(I_n)\right|=2^n \Longrightarrow \left|\mathcal{P}(I_{n+1})\right|=2^{(n+1)}.$
Como $\mathcal{P}(I_n)$ es el conjunto de subconjuntos de $I_n,$ podemos pensar que los subconjuntos de $I_{n+1}$ serán los subconjuntos de $I_n$ a los que también habrá que añadir otro subconjunto por cada subconjunto de $I_n,$ formado por dicho subconjunto y el elemento $n+1:$ \[ S\subset I_{n+1} \Longleftrightarrow \begin{cases} S\subset I_n\\ S=P\cup \left\lbrace n+1 \right\rbrace, \ P\subset I_n\\ \end{cases} \] de manera que $I_{n+1}$ tendrá el doble de subconjuntos que $I_n,$ de modo que $\left|\mathcal{P}(I_{n+1})\right|=2\cdot \left|\mathcal{P}(I_n)\right|$ y aplicando la hipótesis de inducción, esto es $\left|\mathcal{P}(I_{n+1})\right|=2\cdot 2^n=2^{(n+1)}.$


Si definimos $n!=n(n-1)!$ donde $n!$ denota el factorial de $n$ y $1!=1,$ vamos a demostrar que $n!$ es el producto de todos los números menores o iguales que $n:$ $\prod_{i=1}^{n} i.$

1. Si $n=1$ entonces $n!=1.$
2. Supongamos $n!=\prod_{i=1}^{n} i.$ Entonces: $$(n+1)!=(n+1)n!=(n+1)\prod_{i=1}^{n} i=\prod_{i=1}^{n+1} i.$$

Comentarios

Publicar un comentario

Frecuentes

Aplicaciones Lineales, Isomorfismos y Cambio de Base

Recapitulemos un poco antes de comenzar: hemos visto que todo espacio vectorial tiene una base , e.d. un conjunto de vectores linealmente independientes que lo generan. También hemos visto que podemos representar cada vector del espacio mediante sus coordenadas respecto de una base , y que estas pueden ser distintas en función de la base que tomemos. Habíamos dejado planteadas algunas cuestiones sin resolver, como cómo operar con coordenadas y cómo hacer el cambio de coordenadas en función de qué base tomemos. En el post de hoy vamos a resolver estas cuestiones, para lo cual hablaremos de las aplicaciones lineales y de la matriz de cambio de base. APLICACIONES LINEALES En matemáticas, una vez definida una estructura, lo normal es preguntarse cómo pueden ser las aplicaciones entre ese tipo de estructura. El ejemplo que conocemos por ahora es el de aplicaciones entre conjuntos . Las aplicaciones entre dos conjuntos que respetan la estructura de con...
ENTRAR

Recurrencias Lineales no Homogéneas

En el anterior post vimos cómo resolver recurrencias lineales de la forma: $$\begin{align} a_n=B_1 a_{n-1} + \ ... \ + B_{k}a_{n-k}\end{align} $$con $B_j \in \mathbb{R}$ y $B_k \neq 0.$ Es decir, vimos cómo es posible dar una fórmula explícita para $a_n$ que únicamente dependa de $n.$ Estas son las llamadas recurrencias lineales homogéneas. En este post vamos a intentar generalizar y dar una solución explícita para recurrencias que tienen la forma: $$ \begin{align} a_n=B_1 a_{n-1} + \ ... \ + B_{k}a_{n-k} + f(n)\end{align} $$donde $f$ es una función de $\mathbb{N}$ a $\mathbb{R}$ no nula (el caso en el que $f \equiv 0$ es el caso homogéneo que hemos tratado en el anterior post). Estas últimas se conocen como recurrencias lineales no homogéneas. Además en ambos casos los coeficientes $B_j\in \mathbb{R}$ son constantes. Si fueran funciones que dependen de $n$ el tema se complicaría más y no vamos a tratar esos casos por ahora. Por los mismos motivos que en el post anterior, vamos a...
ENTRAR

Relaciones de Orden y de Equivalencia

Vamos a introducir el concepto de lo que es una relación de equivalencia y después veremos lo que es una relación de orden. (La palabra $\text{Def}$ introducirá siempre una nueva definición y $\text{Obs}$ denotará una observación). El post de hoy es un poco más técnico, pero no es difícil de comprender, sobre todo si te animas a coger un papel y un lápiz y comprobar que lo que vamos a ir haciendo tiene sentido. Este tipo de herramientas son de las más básicas en matemáticas y por eso no conviene reducirlas a meros comentarios, puesto que entonces muchos desarrollos carecerían de sentido. Así que no te asustes, y pongámonos manos a la obra. RELACIONES DE EQUIVALENCIA $\text{Def.}$ Dado un conjunto , $X$, una relación de equivalencia, $R$, es una relación binaria en $X$ (relaciona un par de elementos de $X$, digamos $x$ e $y,$ y se lee $xRy:$ $x$ está relacionado con $y$), que cumple las siguientes tres propiedades: Reflexiva:  todo elemento de $X$ está relacionado consigo m...
ENTRAR

El Teorema del Sándwich

Imagen
En el post anterior vimos lo que eran las sucesiones de números reales, los límites de estas y dejamos planteadas algunas preguntas que iremos respondiendo a lo largo de los siguientes posts. Lo que veremos hoy son varios resultados sobre sucesiones de números reales que pueden resultar interesantes e intuitivos y distintos ejemplos de cómo calcular límites de sucesiones utilizando estos resultados. PROPIEDADES DE LOS LÍMITES En el anterior post terminamos hablando de cómo los límites se comportan bien con las operaciones que conocemos en $\mathbb{R},$ pero no demostramos el resultado. Lo que haremos a continuación es investigar un poco una idea que nos va a ayudar a demostrarlo. Vamos a suponer que tenemos dos sucesiones. Una de ellas es constante: $\left\lbrace c_n \right\rbrace_{n=1} ^ \infty, \ \ c_n = c \ \ \forall n \in \mathbb{N}$ para cierto $0<c\in \mathbb{R}$ un número real fijo, y la otra sucesión converge a $0:$  $\left\lbrace a_n \right\rbrace_{n=1}^...
ENTRAR

Aplicaciones y Cardinales

Imagen
APLICACIONES Y FUNCIONES Si acabas de llegar al blog, esta entrada está muy relacionada con la anterior: conjuntos , de modo que leerla te ayudaría a comprender lo que vamos a discutir a continuación. En matemáticas, dados dos conjuntos (digamos $X$ e $Y$), una aplicación de $X$ en $Y$ es una regla que a cada elemento de $X$ le asigna un elemento de $Y$. Digamos que nuestra aplicación se llama $f$, entonces lo denotamos así: $f:X \longrightarrow Y$. La noción de aplicación es muy natural, y no es difícil pensar en ejemplos de aplicaciones: de hecho uno muy habitual es tomando $X=\left\lbrace \text{productos de un supermercado} \right\rbrace$ e $Y=\left\lbrace \text{precios de dichos productos en ese supermercado} \right\rbrace$. Definiendo la aplicación $f:X \longrightarrow Y$ que manda cada producto que puedes comprar en su precio, tenemos una aplicación. Por ejemplo, $f$ lleva una pera en su precio (en ese mercado). En general, si $x$ es un elemento de $X$, e $y$ es...
ENTRAR