Dear

Conjuntos y Combinatoria
Semestre 02/2009 Codigo 300 6822 ´ Escuela de Matem´ ticas a Facultad de Ciencias itbpF1.6362in0.6849in0inlogo.bmp

1 Los Numeros Naturales ´
1.1 Induccion Matem´ tica ´ a
´ No haremos ningun intento de construir los numeros enteros axiom´ ticamente. Por el contrario, suponemos que ya ´ a est´ n dados y que el lector est´ familiarizado con muchos hechos b´ sicossobre ellos. Entre estos, est´ el Principio a a a a de Buen Orden, el cual enunciamos para refrescar la memor´a. ı Todo subconjunto no vac´o S de Z ı S. contiene un elemento m´nimo; esto es, existe un ı

entero a

S tal que a

b, para todo b

´ Es f´ cil probar que el elemento a es unico y se denota por min T. a ´ El Principio de Buen Orden ser´ muy util en la prueba de varias propiedades. Enparticular, lo usaremos para a mostrar que el conjunto de enteros positivos no est´ acotado superiormente, lo que se conoce como la Propiedad a Arquimediana. Teorema 1 ( n a b. ) Si a y b son enteros positivos arbitarios, entonces existe un entero positivo n tal que b, para todo entero positivo

Prueba. Razonemos por el absurdo y supongamos que existen a, b Z tales que n a n. Entonces elconjunto no vac´o ı S b n a n Z est´ contenido en N. Por el a Adem´ s, a , S posee un m´nimo elemento, digamos b ı b m 1 a b m a. m a a b

m a. Notemos que b m a.

m

1

a

S.

Absurdo, pues se contradice la minimalidad de b

´ Con el Principio de Buen Orden disponible, es f´ cil derivar el Primer Principio de Induccion, el cual proporciona a ´ la base para un m´ todo de demostracionllamado e . Teorema 2 ( a 1 S. S, entonces k 1 S. ) Sea S un conjunto de enteros positivos con las siguientes propiedades:

b Para todo entero k : si k

Entonces S es el conjunto de todos los enteros positivos. Prueba. Sea T n Z n/S Z S y supongamos que T es no vac´o. Por el ı , T posee un m´nimo ı ´ elemento, el cual denotamos por a. Dado que 1 S, ciertamente a 1. As´, 0 ı a 1 a. La eleccion de a ´como el menor entero positivo en T implica que a 1 / T. Equivalentemente, a 1 S. Por la hipotesis (b), a a 1 1 S, lo cual contradice que a T. Concluimos que T ∅ y, en consecuencia, S Z . ´ ´ La siguiente es una formula t´pica que se puede establecer por induccion matem´ tica: ı a 12 22 33 n2 n 2n 1 n 6 1 , para n 1, 2, 3, . . . . (1)

Anticipandonos al uso del Tm. ??, denotemos por S elconjunto de enteros postivos que satisfacen la Ec. (??). ´ Observamos que cuando n 1, la formula se convierte en 12 Lo cual significa que 1 modo que 1 1 2 1 1 6 1 .

´ S. A continuacion, supongamos que k 12 22 33 k2 1 k 2k

S (donde k es un entero fijo, pero arbitrario) de 1 k 6 1 . (2)

Para obtener la suma de los primeros k lados de la Ec. (??). Esto nos da 12 22 k2 k 1
2

1 cuadrados, bastaque sumemos el siguiente t´ rmino k e k 2k 1 k 6 k 2k 1 1 6 2k2 7k 6 6 k 1 2k 6 3 k
2

1

2

a ambos

k 6 k

1

k

1

1

k

1

2

.

Por tanto, la Ec. (??) se cumple cuando n k 1. Nuestro razonamiento muestra que el conjunto S contiene el entero ´ k 1 siempre que contiene al entero k. Por el Tm. ??, S tiene que ser igual a Z ; esto es, la formula es verdadera para n 1. ´Nota. Cuando desarrollemos pruebas por induccion matem´ tica, usualmente abreviaremos el ara gumento eliminando cualquier referencia al conjunto S y procederemos a mostrar simplemente que el ´ resultado en cuestion es cierto para el entero 1 y que si es cierto para el entero k, entonces tambi´ n es e cierto para el entero k 1. ´ ´ La prueba de la condicion (a) del Tm. ?? se denomina usualmente elpara la induccion y la prueba de ´ (b) se conoce como el . La hipotesis hecha al realizar el paso inductivo se denomina la . Ejemplo. Demuestre que para todo n 1 se cumple que 1 2 22 21 2n
1

2n

1.

(3)

´ Prueba. Usemos induccion matem´ tica. El paso base es trivial: a 1 1. k: 1. (4)
k 1 k

Para el paso inductivo, supongamos que la Ec. (??) es valida para n 1 Sumando 2k a ambos...