Inducción matemática

Genaro Luna Carreto

Esta página tiene el propósito de explicar la mecánica de las demostraciones por inducción matemática.

Es necesaria una breve introducción.

La inducción matemática es un tipo de demostración que permite probar una cantidad infinita numerable de proposiciones $\mathbf P_i$, donde generalmente, $i\in \mathbb N$. Se apoya en el hecho de que cada número natural puede ser construido mediante la suma sucesiva del número 1. En realidad, lo anterior, es una forma un tanto informal de describir a los naturales. El concepto de conjunto inductivo, permite dar formalidad a tal descripción. La inducción matemática es un principio, un teorema cuya demostración se basa en la idea de conjunto inductivo.

Principio de inducción y ejemplos

Definición

Un conjunto $\cal S$ es llamado inductivo si satisface las dos propiedades siguientes:

• $1\in \cal S$
• Si $x\in \cal S$ entonces $x+1 \in \cal S$

No es difícil convencerse de que existen muchos subconjuntos de reales inductivos. Un ejemplo es nuestro $\mathbb R^{+}$.

Definición

El conjunto de números naturales es la intersección de todos los conjuntos inductivos.

Es posible que consideres un poco exagerada la definición de número natural, pero en cierto momento de la historia fue necesaria una definición de tal índole. El conjunto $\mathbb N$ ya tenía nombre y símbolo, sin embargo ahora conocemos una descripción más adecuada y manejable. Queda como ejercicio mostrar que $\mathbb N$ es también inductivo.

Principio de inducción matemática

Si $\cal T$ es un subconjunto de números naturales que tiene dos propiedades

1. $1\in \cal T$
2. $n\in \cal T$ implica $n+1 \in \cal T$

entonces $\cal T = \mathbb N$

Demostración: El primer lugar, se menciona que $\cal T \subseteq \mathbb N$. Por otro lado, es claro que las propiedades de $\cal T$ lo colocan como inductivo. La definición de $\mathbb N$, como intersección de todos los conjuntos inductivos, lleva a $\mathbb N \subseteq \cal T$. En resumen $\cal T=\mathbb N$.

¿Cómo hacer demostraciones por inducción?

En primer lugar, se debe distinguir una proposición $\mathbf P (n)$ establecida para cada natural $n\geq n_{1}$ ($n_1\in \mathbb N$) ; después deben demostrarse dos cosas:

1. $\mathbf P(n_{1})$ es verdadera
2. $\mathbf P(k)$ implica $\mathbf P(k+1)$

En general, $n_1=1$. A la proposición $\mathbf P(k)$ usualmente se le denomina hipótesis de inducción.

Suponga $x\geq1$. Demuestra por inducción matemática que $$\forall n\in \mathbb N : x^n\geq 1 $$

Demostración

En este caso $$\mathbf P(n): x^n\geq 1.$$ Se desea establecer la veracidad para cualquier número natural, por lo cual $n_{1}=1$. Vayamos por partes:

1. $\mathbf P(1)$ es verdadera

Según lo dado $\mathbf P(1):x^1\geq 1$. Como $x^1=x$ y por hipótesis $x \geq 1$, entonces $\mathbf P(1)$ es verdadera.
2. $\mathbf P(k)$ implica $\mathbf P(k+1)$

En forma equivalente, se tiene que mostrar la implicación $$x^{k}\geq 1 \Rightarrow x^{k+1}\geq 1$$ Suponga que $\mathbf P(k)$ es verdadera, en otras palabras, $x^{k}\geq 1$ es verdadera. Multipliquemos la desigualdad $x^{k} \geq 1$ por el número positivo $x$. Entonces \begin{align*} x^{k}x &\geq 1\cdot x\\ \end{align*} la desigualdad no se invierte pues $x$ es positivo \begin{align*} x^{k+1} &\geq x\\ \end{align*} Las expresiones $x^{k+1}\geq x$ y $x\geq 1$ conducen a $x^{k+1}\geq 1$, que no es otra cosa que $\mathbf P(k+1)$.

Pruebe que $2^n>n$, donde $n \in \mathbb N$.

Demostración

Sin duda $\mathbf P(n):2^n > n $.

1. $\mathbf P(1)$ es verdadera
   
   Tenemos que $\mathbf P(1):2^1 > 1 $. Es obvia la veracidad de $2^1 > 1 $.
2. $\mathbf P(k)$ implica $\mathbf P(k+1)$
   En otra palabras $$2^{k}>k \Rightarrow 2^{k+1}>k+1.$$ Tomando la hipótesis de inducción \begin{align*} 2^{k} &> k\\ 2^{k}\cdot 2 &> 2\cdot k\\ 2^{k+1} &> 2\cdot k \end{align*} Además, en virtud de que $k$ es natural, $k\geq 1$, por tanto $k+k \geq 1+k$, o sea $2k\geq k+1$. En conclusión, $$2^{k+1} > 2 k \geq k+1,$$ por transitividad, $2^{k+1}>k+1$

Desigualdad de Bernoulli.

Suponga ahora que $x>-1$. Muestra por inducción matemática $$\forall n\in \mathbb N: (1+x)^n\geq 1+nx$$

Demostración

1. $\mathbf P(1)$ es verdadera
   
   Resulta que $\mathbf P(1): (1+x)^1\geq 1+1\cdot x$. En razón de $(1+x)^1=1+x$ y $1+1\cdot x=1+x$, entonces $(1+x)^1 \geq 1+1\cdot x$.


2. $(1+x)^k\geq 1+kx \; \Longrightarrow \; (1+x)^{k+1}\geq 1+(k+1)x$
   Multipliquemos la hipótesis de inducción por $1+x$. \begin{align*} (1+x)^k \cdot (1+x) &\geq (1+kx)(1+x)\\ \end{align*} la desigualdad no se invierte pues $x>-1$, o sea $x+1>0$ \begin{align*} (1+x)^{k+1} &\geq 1+x+kx+kx^2\\ (1+x)^{k+1} &\geq 1+kx^2+ (k+1)x \end{align*} Hagamos una pausa. El número $kx^2>0$, pues es multiplicación de positivos; con mayor razón, $1+kx^2>0$. Si a la desigualdad precedente le sumamos $(k+1)x$, entonces $$ 1+kx^2+ (k+1)x>(k+1)x.$$ Conjugando las desigualdades obtenidas $$(1+x)^{k+1} \geq 1+kx^2+ (k+1)x \geq (k+1)x,$$ Finalmente, por transitividad $(1+x)^{k+1}\geq 1+(k+1)x$.

Muestra por inducción matemática que \begin{align}\label{sumanaturales} 1+2+3+4\cdots +(n-1)+n= \frac{n(n+1)}{2} \end{align}

Demostración

De manera que $$\mathbf P(n):1+2+3+4\cdots +(n-1)+n= \frac{n(n+1)}{2}$$

1. $\displaystyle \mathbf P(1): \; 1= \frac{1(1+1)}{2}$ es verdadera
   Es obvio a partir de que el cociente $\frac{1(1+1)}{2}$ es igual a 1.


2. $\mathbf P(k)$ implica $\mathbf P(k+1)$, donde \begin{align*} \mathbf P(k) &: \; 1+2+3+4\cdots +(k-1)+k = \frac{k(k+1)}{2}\\ \mathbf P(k+1) &: \;1+2+3+4\cdots +(k-1)+k+(k+1) =\frac{(k+1)(k+2)}{2} \end{align*} Sumemos $k+1$ en ambos lados de $\mathbf P(k)$ \begin{align*} 1+2+3+4\cdots +(k-1)+k + k+1 &= \frac{k(k+1)}{2}+ k+1\\ &=\frac{k(k+1)+2(k+1)}{2}\\ &=\frac{(k+1)(k+2)}{2} \end{align*} A partir de $\mathbf P(k)$ se ha obtenido $\mathbf P(k+1)$.

6-junio-2014