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:

Proposition 3.1 (Principio de induccion).

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

•

el numero $n=1$ cumple la propiedad $P$ .
•

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

entonces todos los numeros naturales cumplen la propiedad $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 $n=1$ .
2.

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

Veamos un ejemplo:

Theorem 3.2.

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

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

Proof 3.3.

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

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

Suponiendo que es cierto para $n$ , tenemos que demostrar que entonces es cierto para $n+1$ y que $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}}

Definition 3.4 (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 $a_{1}+a_{2}+\cdots+a_{n}$ , en lugar de los puntos suspensivos escribimos

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

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

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

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

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

Un ejemplo es el factorial de $n$ :

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

Example 3.5.

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

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

Proof 3.6.

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

\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 $n$ entonces también es cierto para $n+1$ .

La hipotesis de induccion es: $\displaystyle\sum_{k=1}^{n}\frac{1}{k(k+1)}=\frac{n}{n+1}$ .

La tesis de induccion es: $\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 $n+1$ . Luego el principio de induccion es cierto para todo $n\in\mathbb{N}$ .

Example 3.7.

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

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

Proof 3.8.

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

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

Por otro lado,

\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 $n=1$ , supongamos que también se cumple para $n$ y veamos si es cierto para $n+1$ : $\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 $n+1$ . Por tanto, se cumple el principio de induccion para todo $n\in\mathbb{N}$ y todo $r\neq 1$ .

Example 3.9.

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

Proof 3.10.

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

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

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

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

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

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

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

Como $2\leq n+2\Rightarrow(n+1)!2\leq(n+2)!$ .

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

Example 3.11.

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

Proof 3.12.

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

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 $n$ entonces es cierto para $n+1$ .

Hipotesis de induccion: $2^{2n}+5$ es multiplo de 3.

Tesis de induccion: $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 $n\in\mathbb{N}$ .