(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En esta nota usaremos el quinto axioma de Peano para hacer un tipo de prueba muy frecuente en matemáticas cuando se quiere constatar que un subconjunto $A$ de los números naturales es de hecho igual que los números naturales, es decir que $A=\mathbb N$. Nosotros obtuvimos el quinto axioma de Peano de una definición conjuntista de los números naturales (ver la nota 16), que nos dice que si en un conjunto cualquiera de los números naturales: se cumple que el cero está y que para cualquier elemento del conjunto su sucesor también está, entonces, ese conjunto es el de los números naturales. Hay muchísimos ejemplos donde queremos garantizar que cierta propiedad se cumple para todos los números naturales, así que una forma de hacerlo es considerar la colección de todos los números naturales que cumplen dicha propiedad y usar el quinto axioma de Peano para ver que esa colección es de hecho el conjunto de todos los números naturales.

Procedamos a dar una basta serie de ejemplos donde se usa este principio, en todos ellos probaremos que un subconjunto $A$ de naturales es igual a $\mathbb N$, para ello veremos que

$i)\, 0\in A$ (llamada la base de inducción), y que

$ii)$ si $n\in A$, entonces $n^+=n+1\in A$ (llamado paso Inductivo (PI), para ello supondremos que $n\in A$, hipótesis que se conoce comúnmente como la hipótesis de inducción (HI), y probaremos que $n+1\in A$).

Con estas dos condiciones satisfechas podemos asegurar que $A=\mathbb N$ en virtud del quinto Axioma de Peano.

Ejemplos de demostraciones que usan el principio de inducción

En los siguientes ejemplos veremos cómo se usa el principio de inducción o quinto Axioma de Peano, que justificamos a partir de la definición de los números naturales.

Ejemplos

1. La suma de los primeros $n$ naturales está dada por la fórmula:

$0+1+\dotsc +n=\frac{n(n+1)}{2}$ $\forall n\in \mathbb N.$

Queremos ver que la fórmula anterior se cumple para toda $n$ natural, pero hasta el momento no sabemos que así sea. Podemos entonces considerar el conjunto de naturales para los que sí se cumpla la fórmula, digamos

$A=\set{ n\in \mathbb N \mid 0+1+\dotsc +n=\frac{n(n+1)}{2} }.$

Si logramos probar que en $A$ están todos los naturales, entonces habremos probado que la fórmula se cumple para todos los naturales. Una forma de hacerlo es usando el principio de inducción:

Por demostrar que $A=\mathbb N.$

i) Base de inducción. Por demostrar que $0\in A.$

$0=\frac{0(0+1)}{2}$. Por lo tanto, $0\in A.$

ii) Paso Inductivo. (PI).

Sea $n\in A$, es decir, supondremos que

$0+1+\dotsc +n=\frac{n(n+1)}{2}$.

Ésta es nuestra hipótesis de inducción.

Demostración de que $n^+=n+1\in A$ usando la HI.

Por demostrar que el sucesor de $n$ también está en $A$, es decir por demostrar que $n^+=n+1\in A,$ o de modo equivalente por demostrar que

$0+1+\dotsc +(n+1)=\frac{(n+1)((n+1)+1)}{2}= \frac{(n+1)(n+2)}{2}.$

Usando la hipótesis de inducción sabemos que

$(0+1+\dotsc +n)+(n+1)=\frac{n(n+1)}{2}+(n+1)= \frac{(n)(n+1)+2(n+1)}{2}= \frac{(n+1)(n+2)}{2}.$

Así, $n^+=n+1\in A$ y por el principio de inducción $A=\mathbb N.$

$\square$

Observemos que probar que $0\in A$ fue equivalente a probar que la fórmula que queríamos probar se cumplía para $n=0$. Por otro lado suponer que $n\in A$ fue equivalente a suponer que la fórmula se cumplía para $n$, y demostramos a partir de ello que $n+1\in A$ verificando que la fórmula se cumplía para $n+1$. Así, comúnmente se omite el conjunto $A$ que consiste de todos los naturales que cumplen la propiedad que queremos verificar para todos los naturales y directamente se verifican los siguientes puntos:

$i)$ La propiedad se cumple para $n=0$,

$ii)$ $\forall n\in\mathbb{N}$, si $n$ cumple la propiedad, entonces $n+1$ también la cumple,

y con ello demostramos que todos los números naturales cumplen la propiedad. Veamos más ejemplos.

2. La suma de las potencias consecutivas de dos $2^0+2^1+\dotsc+2^n=2^{n+1}-1$, $\forall n\in \mathbb N.$

i) Base de inducción. Veamos que el cero cumple la fórmula

$2^0=1=2^{0+1}-1$, por lo tanto la formula se cumple para $n=0.$

ii) Paso Inductivo. (PI).

Sea $n\in \mathbb N$. Supongamos que el resultado se cumple para $n$ es decir supongamos que:

$2^0+2^1+\dotsc+2^n=2^{n+1}-1.$

Ésta es nuestra hipótesis de inducción.

Demostración de que se cumple para $n+1$ usando la HI.

Veamos ahora que se cumple para $n+1$. Usando la hipótesis de inducción

$(2^0+2^1+\dotsc+2^n)+2^{n+1}=(2^{n+1}-1)+2^{n+1}=2( 2^{n+1} )-1= 2^{(n+1)+1}-1. $

Por lo tanto,

$2^0+2^1+\dotsc+2^n=2^{n+1}-1$, $\forall n\in \mathbb N.$

$\square$

3. Prueba de que $1+2n<3^{n}$ $\forall n\in \mathbb N$, $n\geq 2$.$\quad\quad\quad *$

Observa que, dado que $n\geq 2$ tenemos que $n=m+2$ para alguna $m\in\mathbb{N}$, así que lo que debemos probar es equivalente a demostrar que:

$1+2(m+2)<3^{m+2}$ $\forall m\in \mathbb N$.$\quad\quad\quad **$

Para ello basta ver que

i) La propiedad ** se cumple para $m=0$,

ii) $\forall m\in\mathbb{N}$, si $m$ cumple la propiedad **, entonces $m+1$ también cumple la propiedad **.

Pero el que ** se cumpla para $m+1$ significa que $1+2((m+1)+2)<3^{(m+1)+2}$, es decir que $1+2((m+2)+1)<3^{(m+2)+1}$. Así, debemos ver que

i) La propiedad ** se cumple para $m=0$,

ii) $\forall m\in\mathbb{N}$, si $1+2(m+2)<3^{m+2}$, entonces $1+2((m+2)+1)<3^{(m+2)+1}$,

y como $n=m+2,$ escribiendo todo en términos de $n$ esto es equivalente a probar que

i) Base de inducción. La propiedad * se cumple para $n=2$,

ii) Paso Inductivo. (PI).

$\forall n\in\mathbb{N}$ con $n\geq 2$, si $1+2n<3^{n}$, entonces $1+2(n+1)<3^{n+1}.$

Así, cuando queramos probar una afirmación para todos los naturales a partir de un valor $k$, bastará con realizar el proceso de inducción de la manera usual sólo que la base de inducción se trabajará con $n=k$ en vez de $n=0$.

Escribamos ahora sí la prueba del ejercicio:

i) Base de inducción. Para $n=2$

$1+2(0+2)<3^{(0+2)}$ es verdadero pues

$1+2(0+2)=5<9=3^2.$

ii) Paso Inductivo. (PI).

Supongamos que el resultado se cumple para $n\geq 2$, es decir supongamos que $1+2n<3^n$.

Ésta es nuestra hipótesis de inducción.

Demostración de que se cumple para $n+1$ usando la HI.

Veamos ahora que se cumple para $n+1$, es decir mostremos que $1+2(n+1)<3^{n+1}.$

Multiplicando la HI por $3$ tenemos que

$3+6n=3(1+2n)<3(3^n)=3^{n+1}.$

Basta ver que $1+2(n+1)<3+6n$. Como $n\geq 2$, entonces $0<4n$ pero:

$0<4n\Longleftrightarrow 2n<6n \Longleftrightarrow 3+2n<3+6n \Longleftrightarrow 1+2(n+1)<3+6n.$

Así, $1+2(n+1)<3+6n$.

Tenemos entonces que $1+2(n+1)<3+6n$ y que $3+6n<3^{n+1}$ por lo que concluimos que:

$1+2(n+1)<3^{n+1},$

que es lo que queríamos probar.

Por lo tanto $1+2(n+1)<3^{n+1}$ $\forall n\in \mathbb N$, $n\geq 2$.

$\square$

A continuación enunciaremos el segundo principio de inducción y su equivalente el principio de buen orden.

Segundo principio de inducción (inducción fuerte o modificada)

Si $A\subseteq \mathbb N$ es tal que:

Para toda $n$, si $m\in A$ para toda $m<n$, entonces $n\in A.$

Concluimos que $A=\mathbb N$.

Principio del buen orden PBO

Si $A$ es un subconjunto no vacío de $\mathbb N$, entonces $A$ tiene un elemento menor o igual a los demás. Es decir si $A\subseteq \mathbb N$, $A\neq \emptyset$, entonces existe $m\in A$, tal que $m\leq a$ $\forall a\in A$.

Nota. El segundo principio de inducción y el principio del buen orden son equivalentes y ambos se pueden probar con el principio de inducción.

Ejemplo del segundo principio de inducción

Considera la sucesión de Fibonacci:

$1,1,2,3,5,8,\dotsc $

dada por

$F_0=F_1=1$

$F_{n+2}=F_n+F_{n+1} \,\forall n\in\mathbb{N}$

Veamos que $F_n\leq 2^n$ $\forall n\in \mathbb N$.

Sea $n\in \mathbb N.$ Supongamos que $F_m\leq 2^m$ $\forall m\in \mathbb N$ con $m<n.$

Por demostrar que

$F_n\leq 2^n.$

Si $n=0$ o $n=1$

$F_0=1=2^0$, $F_1=1<2^1=2$.

Podemos suponer entonces que $n>1$, así $n\geq 2.$

Entonces $n=2+k$, con $k\in \mathbb N$ y así

$F_n=F_{2+k}=F_k+F_{k+1}$ que por hipótesis de inducción es menor que $2^k+2^{k+1}$. Concluimos que:

$F_n=F_{2+k}=F_k+F_{k+1}\leq 2^k+2^{k+1} =2^k(1+2)= 2^k(3)< 2^k(4)= 2^k(2^2)=2^{k+2}=2^n.$

Por lo tanto $F_n\leq 2^n$ $\forall n\in \mathbb N.$

Tarea Moral

1. Prueba que para toda $n\in \mathbb N$

$\sum_{k=0}^{n}k^2=\frac{n(n+1)(2n+1)}{6}.$

2. Prueba que para toda $n\in \mathbb N$, $n<2^n.$

3. Prueba que la suma de los ángulos internos de un polígono de $n$ lados es $(n-2)180$ usando inducción sobre $n$.

4. Considera la secuencia definida de manera recursiva como:

$f_0=1$, $f_{n+1}=f_n+\dotsc+f_0+1.$

Prueba que $f_n=2^n$ para toda $n\in \mathbb N$.

Más Adelante

Ahora que ya estamos más familiarizados con las pruebas por inducción, en la siguiente nota continuaremos usando el quinto Axioma de Peano para realizar demostraciones y probaremos de esta forma las propiedades de la suma y el producto de los números naturales.

Enlaces relacionados.

Página principal del curso.

Nota anterior. Nota 17. El orden en los números naturales.

Nota siguiente. Nota 18b. Demostraciones por inducción de las propiedades de las operaciones de los números naturales.