PRINCIPIO DE INDUCCION MATEMATICA

En este corto e importante captulo se trabajara los principios de induccionmatematica: Principio de induccion matematica debil y fuerte. Nos concentramosen el primero pues es el de mas uso en matematica. Dejamos al lector profundizaren el uso del principio de induccion fuerte. Esta herramienta como tecnica de de-mostracion permite demostrar resultados en el conjunto de los enteros positivos.

0.1. Principio de Induccion debil

Es importante conocer el principio de induccion debil y su demostracion. Paraello es necesario involucrar ciertos axiomas y teoremas que nos permiten llevar acabo tal prueba. Estos son los siguientes:

Axioma de buen orden (Buen Ordenamiento): Sea S 6= , S Z+. Entoncesexiste un m S tal que m x, x S. A este elemento se le denominamnimo de S.

Con tus propias palabras, que significa el ABO?

Teorema 0.1 1 es el mnimo elemento en Z+.

DemostracionSea S = {x Z+ : 0 < x < 1}. Por teorema demostrado sabemos que 1 Z+.Veamos dos casos:

1. Si S = entonces 1 es el mnimo.2. Si S 6= , entonces por ABO, existe un m S tal que m < x, para todo

x S. As, 0 < m < 1 de donde 0 < m2 < 1 y as, 0 < m2 < m < 1. De esto,m2 < m e indica que m2 es el mnimo de S lo cual contradice la eleccion dem como el mnimo. Esto nos permite concluir que 1 es el mnimo.

1

Induccion 2

Corolario 1 Si n Z, entonces no existe un k Z tal que n < k < n + 1.DemostracionArgumentemos por contradiccion y supongamos que existe tal k. Como n < k 1 implica m 1 > 0. Pero 0 < m 1 < m de talforma que m1 / T . Esto implica que m1 S. Por hipotesis (m1)+1 = m Slo cual es una contradiccion pues m es el mnimo de T . Por tanto, S = Z+Al estudiar propiedades de Z+, se usa el siguiente principio:

Teorema 0.3 Sea P (n) una propiedad que se enuncia para enteros positivos ycumple:

1. P (1) es verdadera

2. Siempre que P (k) sea verdadera se tiene que P (k + 1) es verdadera.

Entonces P (n) es verdadera para todo n Z+.DemostracionSea S = {n Z+ : P (n) es verdadera}. Luego, 1 S y k + 1 S. Por teoremaanterior, S = Z+. As, P (n) es verdadera para todo entero positivo.Ilustramos con el siguiente ejemplo el uso del principio de induccion matematica.

Ejemplo 0.1 Demostrar 1 + 2 + . . . + n =n(n + 1)

2.

Ejemplo 0.2 Demuestre que 2n > n2 para todo n entero mayor que 4.Solucion:Consideremos el predicado sobre Z+ P (n) : 2n > n2. Demostremos por induccionque P (n) es valido para todo n Z+.

Caso base. Si n = 1 entonces P (5) : 25 = 32 > 52 = 25 el cual es verdadero.

Induccion 3

Hipotesis inductiva. Supongamos que P (k) : 2k > k2 es valido para algunk Z+. Demostremos que el enunciado P (k + 1) : 2k+1 > (k + 1)2.2k+1 = 2 2k > 2 k2 pues 2k > k2 por hipotesis inductiva.Entonces, 2k+1 = 22k > 2k2 = k2+k2 > k2+4k pues, al ser k > 4 se cumpleque kk = k2 > 4k. Ademas, el que k > 4 tambien implica 2k > 8 y 8 > 1 en-tonces 2k > 1 y de esto 2k+2k > 2k+1 de donde 4k > 2k+1. Volviendo a ladesigualdad anterior,2k+1 = 2 2k > 2 k2 = k2 + k2 > k2 + 4k = k2 + 2k + 1 = (k + 1)2.De esta forma, P (k + 1) es tambien valida. Por lo tanto, P (n) es validopara todo n Z+.

Ejemplo 0.3 Demuestra que n! < nn para todo entero n mayor que 1.Solucion:Sea P (n) : n! < nn. Demostremos por induccion que P (n) es valido para todoentero positivo. Si n = 2 entonces P (2) : 2! < 22 es valido. Supongamos queP (k) : k! < kk es un enunciado verdadero para algun k Z+ y demostremos queP (k + 1) : (k + 1)! < (k + 1)k+1 es verdadero. Como k > 1 entonces k + 1 > 0.Por otro lado, (k + 1)! = k!(k + 1) < kk(k + 1). Como k > 1 entonces k < k + 1y as, kk < (k + 1)k y al tomar lo anterior, (k + 1)! = k!(k + 1) < kk(k + 1) 3.5. Prueba que si x 0 entonces 1 + nx (1 + x)n.6. Prueba que 2n < n!

7. Demuestra que 12 22 + 32 . . . + (1)n1n2 = (1)n1n(n + 1)2

para n

entero positivo.

8. Determina a partir de que numero entero, la cantidad n27n+12 es no neg-ativo. Demuestra por induccion que a partir del numero que determinaste,tal cantidad es no negativa.

9. Pruebe que 2 + 4 + 6 + . . . + 2n = n(n + 1) para todo n Z+.10. Pruebe que n < 2n para todo n Z+.

11. Pruebe que 1 + 3 + 9 + . . . + 3n =3n+1 1

2para todo n Z+.

12. Pruebe que 13 + 23 + . . . + n3 =

[n(n + 1)

2

]2para todo n Z+.

13. Suma de una progresion geometrica finita: a + ar + ar2 + . . . + arn1 =a(1 rn)

1 r , con a, r R y n Z+.