Induccion

N´ meros Naturales u

1

N´ meros Naturales u
N = {1, 2, 3, 4, ......}.

En este curso denotaremos por N el conjunto de los n´meros naturales. Es decir u

No daremos una construcci´n formal de los n´meros naturales. S´lo daremos algunas propiedades que todos conocemos o u o y que bastan para nuestros prop´sitos. o 1. Los N´meros naturales se pueden sumar y multiplicar. Es decir la suma yel producto de dos n´meros naturales u u es un n´mero natural. u No siempre se pueden restar obteniendo como resultado un natural. Por ejemplo 3 − 5 = −2 ∈ N. / Tampoco se pueden siempre dividir obteniendo como resultado un n´mero natural. Por ejemplo 1 dividido por 2 u no es un n´mero natural. u 2. Los n´meros naturales estan ordenados de acuerdo al orden que todos conocemos. Por ejemplo 135 esmenor que u 343. Usualmente escribiremos 135 < 343. 3. La propiedad siguiente es importante para la demostraci´n del Principio de Inducci´n. o o Todo subconjunto no vac´ de N tiene un elemento m´ ıo ınimo. Ejemplo: a) Si A = {n ∈ N/n es par } entonces el elemento m´ ınimo de A es 2. ınimo de A es 94. b) Si A = {n ∈ N/n > 93} entonces el elemento m´ c) Si A = {n ∈ N/n es m´ltiplo de 7 y mayor que32} entonces el elemento m´ u ınimo de A es 35. d) Si A = {n ∈ N/n primo mayor que 20} entonces el elemento m´ ınimo de A es 23. 4. Todo n´mero natural tiene un sucesor. Si n ∈ N entonces el sucesor de n es por definici´n n + 1. u o Ejemplo: a) El sucesor de 345 es 346. b) El sucesor de 1 es 2. c) Cual es el sucesor del sucesor de 1238 ? 5. Todo n´mero natural distinto de 1 tiene un antecesor. Si n∈ N entonces el antecesor de n es por definici´n n − 1. u o Ejemplo: a) Cual es el antecesor de 1238 ? b) Cual es el antecesor del antecesor de 1238 ?

1

2

El Principio de Inducci´n o

Comenzaremos esta secci´n con un ejemplo de deducci´n recursiva con el fin de entender lo que es la Inducci´n. o o o Ejemplo: Se tiene n puntos en el plano de modo que ninguna terna de ellos es colineal.Cuantas rectas pueden ser trazadas de modo que unan cada par de puntos? Soluci´n: o Si n = 1 el problema no tiene sentido. Si n = 2 entonces hay una sola recta. Si n = 3 entonces hay 3 rectas. Haciendo un dibujo podemos ver que si n = 4 entonces hay 6 rectas. Podr´ ıamos continuar haciendo dibujos para los casos n = 5, n = 6, .....,etc. Pero, Ser´ Ud. capaz de contar en el ıa dibujo el n´mero derectas para el caso n = 1993? u Por lo tanto para resolver este problema demos recurrir a un m´todo mas inteligente. e Se propone lo siguiente. Si yo s´ que para n = 4 hay 6 rectas, me resulta muy f´cil saber el n´mero de rectas para el e a u sucesor de n = 4 que es n = 5. En efecto si tenemos 5 puntos en plano elijamos 4 de ellos y excluyamos uno. Nos quedan 4 puntos. Para estos 4 puntos ya sabemosque hay 6 rectas que unen todos los pares de estos 4 puntos. Cu´ntas rectas a nos faltan ahora que unan todos los pares de los 5 puntos. La respuesta es sencilla. Estan todas las rectas que unen los 4 puntos elegidos, que ya sabemos son 6, MAS las rectas que unen el punto excluido con cualquiera de los puntos de los puntos elejidos, estas son 4. Por lo tanto el n´mero de rectas en el caso n = 5 es 6+ 4 = 10. Como ejercicio calcule, a u partir de que el n´mero de rectas para n = 5 es 10, el n´mero de rectas en el caso n = 6. u u Ahora la idea est´ clara. Si sabemos que el n´mero de rectas para el caso de n puntos es un n´mero que denotamos a u u por L(n), podemos deducir, mediante esta idea de excluir un punto, el n´mero L(n + 1) de rectas en el caso de n + 1 u puntos. M´s precisamente a L(n+ 1) = L(n) + n As´ como sabemos que L(2) = 1, obtenemos L(3) = 1 + 2 = 3, y sucesivamente L(4) = 1 + 2 + 3 = 6, L(5) = ı, 1 + 2 + 3 + 4 = 10, L(6) = 1 + 2 + 3 + 4 + 5 = 15, ..............., L(n) = 1 + 2 + 3 + 4 + ........ + (n − 1). En el ejercicio anterior hemos contado el n´mero de rectas usando la siguiente idea. Si uno conoce el n´mero de rectas u u para el caso de n puntos entonces, con...