3 El principio de inducción matemática

La induccion es un metodo de demostracion basado en uno de los axiomas de los numeros naturales:

Proposición 3.1 (Principio de induccion).

Si $\displaystyle P$ es una propiedad de forma que se cumple simultaneamente:

el numero $\displaystyle n=1$ cumple la propiedad $\displaystyle P$ .
siempre que un cierto numero $\displaystyle n\in\mathbb{N}$ cumple la propiedad $\displaystyle P$ , el siguiente numero $\displaystyle(n+1)$ también cumple la propiedad $\displaystyle P$ .

entonces todos los numeros naturales cumplen la propiedad $\displaystyle P$ .

Este principio nos da una técnica para probar que un teorema es cierto para todos los numeros naturales, que basta con seguir los siguientes pasos:

1.

Comprobar que el resultado es cierto para $\displaystyle n=1$ .
2.

Suponiendo que el resultado es cierto para un numero natural $\displaystyle n$ (se suele llamar <<hipotesis de induccion>>), demostramos que necesariamente el resultado tambien es cierto para $\displaystyle n+1$ .

Veamos un ejemplo:

Teorema 3.1.

Demostrar que para cualquier numero natural $\displaystyle n\in\mathbb{N}$ se cumple que

\displaystyle 1+2+3+\cdots+n=\frac{n(n+1)}{2}

Demostración.

Lo demostraremos por induccion sobre $\displaystyle n$ . En primer lugar, veamos que se cumple para $\displaystyle n=1$ .

\displaystyle 1+2+3+\cdots+n\overset{n=1}{=}1=\frac{1(1+1)}{2}=\frac{n(n+1)}{2}

Suponiendo que es cierto para $\displaystyle n$ , tenemos que demostrar que entonces es cierto para $\displaystyle n+1$ y que $\displaystyle 1+2+\cdots+n+(n+1)=\frac{(n+1)(n+2)}{2}$

1+2+3+\cdots+n+(n+1)=\frac{n(n+1)}{2}+(n+1)=\\ =\frac{n(n+1)+2(n+1)}{2}=\boxed{\frac{(n+1)(n+2)}{2}}

∎

Definición 3.1 (Sumatorio y productorio).

En las formulas relacionadas con sumas o productos de una sucesion de numeros, se utiliza una notacion especial para evitar ambiguedades: los sumatorios y productos. Esta notacion usa dos letras griegas mayusculas: sigma y pi.

1.

Si queremos denotar la suma $\displaystyle a_{1}+a_{2}+\cdots+a_{n}$ , en lugar de los puntos suspensivos escribimos

$\displaystyle\sum_{i=1}^{n}a_{i}$

Esta expresion quiere decir que sumamos los elementos de la sucesion $\displaystyle(a_{i})$ donde $\displaystyle i$ recorre todos los valores enteros entre $\displaystyle i=1$ e $\displaystyle i=n$ .
2.

Si queremos denotar el producto $\displaystyle a_{1}\cdot a_{2}\cdot\ldots\cdot a_{n}$ en lugar de los puntos suspensivos escribiremos

$\displaystyle\prod\limits_{i=1}^{n}a_{i}.$

Esta expresion quiere decir que multiplicamos los elementos de la sucesion $\displaystyle(a_{i})$ donde $\displaystyle i$ recorre todos los valores enteros entre $\displaystyle i=1$ e $\displaystyle i=n$ . Un ejemplo es el factorial de $\displaystyle n$ :

$\displaystyle\prod\limits_{i=1}^{n}i=1\cdot 2\cdot\ldots\cdot n=n!$

Ejemplo.

Demostrar que para todo $\displaystyle n\in\mathbb{N}$ se cumple que

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

Demostración.

Lo demostraremos por induccion sobre $\displaystyle n$ . En primer lugar, comprobamos si se cumple para $\displaystyle n=1$ .

\displaystyle\begin{rcases}\sum_{k=1}^{n}\frac{1}{k(k+1)}=\sum_{k=1}^{1}\frac{% 1}{k(k+1)}=\frac{1}{1(1+1)}=\frac{1}{2}\\ \frac{n}{n+1}=\frac{1}{1+1}=\frac{1}{2}\end{rcases}\Rightarrow\text{ Cierto % para }n=1

Ahora, demostramos que si es cierto para $\displaystyle n$ entonces también es cierto para $\displaystyle n+1$ . La hipotesis de induccion es: $\displaystyle\displaystyle\sum_{k=1}^{n}\frac{1}{k(k+1)}=\frac{n}{n+1}$ . La tesis de induccion es: $\displaystyle\displaystyle\sum_{k=1}^{n+1}\frac{1}{k(k+1)}=\frac{n+1}{n+2}$ .

\sum_{k=1}^{n+1}\frac{1}{k(k+1)}=\sum_{k=1}^{n}\frac{1}{k(k+1)}+\frac{1}{(n+1)% (n+2)}=\frac{n}{n+1}+\\ +\frac{1}{(n+1)(n+2)}=\frac{n(n+2)+1}{(n+1)(n+2)}=\frac{n^{2}+2n+1}{(n+1)(n+2)% }=\\ =\frac{(n+1)^{2}}{(n+1)(n+2)}=\frac{n+1}{n+2}

Asi, llegamos a que tambien se cumple para $\displaystyle n+1$ . Luego el principio de induccion es cierto para todo $\displaystyle n\in\mathbb{N}$ . ∎

Ejemplo.

Probar que si tenemos $\displaystyle r\neq 1$ y $\displaystyle n\in\mathbb{N}$ cualesquiera, entonces

\displaystyle 1+r+r^{2}+\cdots+r^{n}=\sum_{j=0}^{n}r^{j}=\frac{r^{n+1}-1}{r-1}

Demostración.

Lo demostraremos por induccion sobre $\displaystyle n$ (numero natural). Para ello, comprobamos primero si se cumple para $\displaystyle n=1$ .

\displaystyle\sum_{j=0}^{n}r^{j}\overset{n=1}{=}\sum_{j=0}^{1}=1+r

Por otro lado,

\displaystyle\frac{r^{n+1}-1}{r-1}=\frac{r^{2}-1}{r-1}=\frac{(r+1)(r-1)}{r-1}=% r+1=1+r

Como se cumple para $\displaystyle n=1$ , supongamos que también se cumple para $\displaystyle n$ y veamos si es cierto para $\displaystyle n+1$ : $\displaystyle\displaystyle\sum_{j=0}^{n+1}r^{j}=\frac{r^{n+2}-1}{r-1}$ .

\sum_{j=0}^{n+1}r^{j}=\sum_{j=0}^{n}r^{j}+r^{n+1}=\frac{r^{n+1}-1}{r-1}+r^{n+1% }=\frac{r^{n+1}-1+r^{n+1}(r-1)}{r-1}=\\ =\frac{r^{n+1}-1+r^{n+2}-r^{n+1}}{r-1}=\boxed{\frac{r^{n+2}-1}{r-1}}.

Hemos llegado a que la proposicion es cierta para $\displaystyle n+1$ . Por tanto, se cumple el principio de induccion para todo $\displaystyle n\in\mathbb{N}$ y todo $\displaystyle r\neq 1$ . ∎

Ejemplo.

Demostrar que para todo $\displaystyle n\in\mathbb{N}$ se cumple que $\displaystyle 2^{n}\leq(n+1)!$

Demostración.

Lo demostraremos por induccion sobre $\displaystyle n$ . En primer lugar, comprobamos si es cierto para $\displaystyle n=1$ .

\displaystyle 2^{n}\leq(n+1)!\Rightarrow 2^{1}\leq(1+1)!=2\leq 1\cdot 2=2\leq 2

Como se cumple para $\displaystyle n=1$ , supongamos que es cierto para $\displaystyle n$ y veamos que tambien se cumple para $\displaystyle n+1$ .

\displaystyle 2^{n+1}=2^{n}\cdot 2\leq(n+1)!\cdot 2

Tenemos que probar que $\displaystyle(n+1)!\cdot 2\leq(n+2)!$

\displaystyle(n+1)!\cdot 2=1\cdot 2\cdot\ldots\cdot(n+1)\cdot 2

\displaystyle(n+2)!=1\cdot 2\cdot\ldots\cdot(n+1)\cdot(n+2)

Como $\displaystyle 2\leq n+2\Rightarrow(n+1)!2\leq(n+2)!$ . Entonces, $\displaystyle 2^{n+1}\leq(n+2)!$ y se cumple el teorema para todo $\displaystyle n\in\mathbb{N}$ . ∎

Ejemplo.

Probar que si $\displaystyle n\in\mathbb{N}$ entonces $\displaystyle 2^{2n}+5$ es un multiplo de 3.

Demostración.

Lo probaremos por induccion sobre $\displaystyle n$ . En primer lugar, comprobamos si es cierto para $\displaystyle n=1$ .

\displaystyle 2^{2n}+5\overset{n=1}{=}2^{2}+5=4+5=9\Rightarrow\text{ multiplo % de 3 }

Ahora, tendremos que demostrar que si es cierto para $\displaystyle n$ entonces es cierto para $\displaystyle n+1$ . Hipotesis de induccion: $\displaystyle 2^{2n}+5$ es multiplo de 3. Tesis de induccion: $\displaystyle 2^{2(n+1)}+5$ es multiplo de 3. En este caso:

2^{2(n+1)}+5=2^{2n+2}+5=2^{2n}\cdot 2^{2}+5=2^{2n}\cdot 4+5=(2^{2n}+5)+2^{2n}% \cdot 3=\\ =3\cdot 2^{n}+3q=\underbrace{3(2^{2n}+q)}_{\text{multiplo de 3}}

Por tanto, por el principio de induccion la formula es valida para todo $\displaystyle n\in\mathbb{N}$ . ∎