Mat021-Apunte Induccion Ayud Mauricio Godoy

8/2/2019 Mat021-Apunte Induccion Ayud Mauricio Godoy

1/5

Acerca del Principio de Induccion.

Mauricio Godoy Molina

Marzo, 2005

Resumen

Un poco mas de detalle en el principio de induccion completa no le

hace mal a nadie, de hecho quienes tengan entre sus filas a estudiantes

de Informatica o Telematica deberan poner principal atencion a la

formalizacion de ciertos conceptos.

1 Conjuntos Acotados de Z.

Parece natural el querer definir ciertos conceptos antes de entrar de lleno(aunque ni tan de lleno) en temas asociados con los numeros naturales y

enteros. Antes de comenzar con las definiciones, propiedades y teoremasquisiera comentar que la construccion axiomatica de los numeros naturalestiene dos padres: Richard Dedekind y Giuseppe Peano. Se preguntarancual es la diferencia entre uno y otro? La respuesta, aunque muy simple aprimera vista, causa una gran diferencia en la construccion: Peano consideraal 0 como elemento de N, mientras que Dedekind considera como elementoinicial al 1. Para mas detalles de la construccion de Dedekind, que yo noexplicitare aqu, pueden consultar [1].

Definicion 1.1 El conjunto de los numeros naturales N se define como:

1 NSi n N = (n + 1) N

Observacion: La definicion de los numeros naturales, as como muchasotras se conocen como Definiciones Recursivas, es decir, aquellas queutilizan valores previos para determinar elementos futuros.

1


2/5


3/5

2 Principio de Induccion

Una vez conocidos los resultados anteriores (que permiten determinar ele-mentos minimales y maximales en subconjuntos acotados de Z) podemosverificar bastantes resultados, por ejemplo, de la Teora de Numeros (paramas detalles, ver [2]). En particular nosotros estamos interesados en el sigu-iente

Teorema 2.1 (Principio de Induccion) Consideremos que P(m) es unapropiedad, m N Supongamos:

1. P(1) es verdad.

2. m N vale que: Si k {1, 2, . . . , m 1} P(k) es verdad, entoncesP(m) es verdad.

Entonces P(m) vale m N.

Demostracion 2.1 Consideremos el siguiente conjunto:

L = {m N : P(m) es falsa} Z

Es claro que L tiene cota inferior (por ejemplo, el 0). Por el Corolario 1.2 setiene que l L tal que m L : m l. Claramente 1 / L (por hipotesis),

por lo tanto, l 2. Ademas, por la definicion de l se tiene que

m {1, 2, . . . , l 1} = P(m) vale, pues l es cota inferior de L

Luego, por hipotesis inductiva, debera ocurrir que P(l) vale, por lo tantol / L. Es decir, L = .

3 Ejemplos de Induccion:

1. Usemos el Principio de Induccion para demostrar un clasico:

1 + 2 + . . . + n =n(n + 1)

2

Solucion:

n = 1 Evidentemente 1 =1 2

2= 1.

3


4/5

n = k Hipotesis inductiva: 1 + 2 + . . . + k =k(k + 1)

2.

n = k + 1 1 + 2 + . . . + k + (k + 1) =k(k + 1)

2+ (k + 1) =

= (k + 1)

k

2+ 1

=

(k + 1)(k + 2)

2.

2. Verifique usando induccion la desigualdad de Bernoulli:

1 + nx (1 + x)n, x 0

Solucion:

n = 1 Claramente: 1 + 1 x (1 + x)1.

n = k Hipotesis inductiva: 1 + kx (1 + x)k.

n = k + 1 (1 + x)k+1 = (1 + x)(1 + x)k (1 + x)(1 + kx) =

= 1 + x + kx + kx2 1 + (k + 1)x.

3. Verifique usando el principio de induccion que:

n3

+ 2n es divisible por 3

Solucion:

n = 1 13 + 2 1 = 3.

n = k k3 + 2k = 3p(k).

n = k + 1 (k + 1)3 + 2(k + 1) = k3 + 3k2 + 3k + 1 + 2k + 2 =

= 3p(k) + 3(k2 + k + 1) = 3(p(k) + k2 + k + 1)

4. Verifique que 7 es el ultimo dgito del numero

22n

+ 1, n > 1

Solucion:

n = 2 222

+ 1 = 17.

4


5/5

n = k 22k

+ 1 = 10p(k) + 7.

n = k + 1 22k+1 + 1 = (22k)2 + 1 = (10p(k) + 7 1)2 + 1 =

= 100p2(k) + 120p(k) + 36 + 1 = 10(10p2(k) + 12p(k) + 3) + 7.

5. Notemos que podemos demostrar por induccion afirmaciones simple-mente imbeciles, por ejemplo:

Qeremos demostrar que n = n + 1 (lo cual es una estupidez). Supon-gamos la hipotesis inductiva k = k + 1 y demostramos para n = k + 1teniendo (k + 1) = (k + 1) + 1. Evidentemente el problema es que noevaluamos en un valor de partida. Claramente la afirmacion es falsapara n = 1 pues, que se sepa 1 = 2.

Observacion: Cuando el primer valor que sirve para comenzar el procesode induccion (como en los primeros ejemplos) se habla de Induccion Com-pleta, en caso contrario, como en el ejemplo 4., decimos que es InduccionIncompleta.

Referencias

[1] Que son los Numeros?. Rolando Chuaqui. Traduccion de Was sind undwas sollen die zahlen de Richard Dedekind. Fascculos para la Com-prension de las ciencias y las Humanidades. Editorial Universitaria.(1980).

[2] An Introduction to the Theory of Numbers. Ivan Niven and Herbert Zuck-erman. John Wiley and Sons Inc. (1966).

5

Documents

Mat021-Apunte Induccion Ayud Mauricio Godoy