Induccion

´ ´ INDUCCION MATEMATICA
´ ´ ´

´ 1. INTRODUCCION El m´todo deductivo, muy usado en matem´tica, obedece a la siguiente idea: “ e a A partir de un cierto conjuntos de axiomas aceptados sin demostraci´n y de reglas o o l´gicas no contradictorias, se deducen otros enunciados llamados teoremas combinando los axiomas y respetando en cada etapa las reglas l´gicas”. o Otro m´todo para demostrarresultados generales que dependen en alg´ n sentido e u u o e de los n´ meros naturales es conocido con el nombre de Inducci´n Mat´matica . Esta dependencia de los n´ meros naturales significa: se sabe que una determinada u afirmaci´n es verdadera para algunos casos particulares y surge la pregunta. ¿ Dicha o afirmaci´n sigue siendo verdadera para los infinitos n´ meros naturales restante ?. o u Existenmuchas afirmaciones que s´lo son v´lidas para un n´ mero finito de casos o a u y en consecuencia son falsas para un n´ mero infinitos de situaciones. Sin embargo, u podemos encontrar proposiciones (afirmaciones) que son verdaderas s´lo a partir de o un cierto n´ mero natural n0 , de ser asi, la t´cnica que se desarrollaremos se llama u e Inducci´n Incompleta. Para demostrar que una proposici´n p(n) ,∀n ∈ M ⊆ N, o o es verdadera es necesario comprobar la validez de ella para todos los elementos del conjunto M . En el caso en que M = N, diremos que es una Inducci´n Completa. o Si se requiere demostrar la falsedad de una cierta proposici´n p(n), ∀n ∈ M ⊆ N, o es suficiente indicar un elemento particular m ∈ M de manera que p(m) sea falsa. ( Construcci´n de un contra ejemplo). o Ejemplo 1. ∀n ∈ N, n2− 3n − 1 < 0 Es f´cil probar que esta desigualdad es verdadera para n = 1, 2, 3. Sin embargo, a para n = 4 no se cumple ya que 42 − 3 · 4 − 1 = 3 > 0. N´tese que este ejemplo o sencillo muestra que una proposici´n puede ser verdadera para los primeros n´meros o u naturales, sin embargo, es falsa , para n´meros naturales m´s grandes. u a

Copyright 2004, Derechos reservados, no ´sta permitido lareproducci´n parcial o total de este e o material sin el permiso de sus autores .
1

2

´ ´ INDUCCION MATEMATICA

Otros ejemplos: Es f´cil probar que esta proposici´n es verdadera para n = 1, 2, 3. Sin embargo, a o para n = 4 no se cumple dado que (2·4−1)(2·4+1)(2·4+3) = 693. no es divisible por 5 Ejemplo 3. (Ejemplo dado por Leonhard Euler (1707-1783) Consideremos el polinomio cuadr´ticop(n) = n2 + n + 41 y determinemos su valor a para ciertos n ∈ N n : 1 2 3 4 5 6 7 8 n2 + n + 41 : 43 47 53 61 71 83 97 113 Ejemplo 2. ∀n ∈ N, (2n − 1)(2n + 1)(2n + 3), es divisible por 5.

N´tese que todos los n´meros que se obtienen son primos. Se podr´a esperar que o u ı este polinomio cuadr´tico continua generando n´meros primos. Desafortunadamente a u u no es asi, para n = 40, se tiene 1681= 412 , que no es un n´mero primo, luego la 2 proposici´n que ∀n ∈ N, n + n + 41 es un n´mero primo resulta falsa. o u 2. Principio de inducci´n Matem´tica o a Una proposici´n p(n) es verdadera para todos los valores de la variable o n si se cumplen las siguientes condiciones : Paso 1.- La proposici´n p(n) es verdadera para n = 1 , o bien, p(1) es verdadera. o Paso 2.- Hip´tesis de Inducci´n . Sesupone que p(k) es verdadera , donde k es un o o n´ mero natural cualesquiera. u Paso 3.- T´sis de Inducci´n. Se demuestra que p(k + 1) es verdadera, o bien, e o p(k) verdadera ⇒ p(k + 1) verdadera. La t´cnica de Inducci´n Matem´tica consiste en los tres pasos anteriores. Si se e o a necesita demostrar la validez de una proposici´n p(n) para todos los valores naturales o n, entonces es suficienteque se cumplan: Paso 1, Paso 2 y Paso 3 . Comentario: Intuitivamente la idea anterior se conoce con el nombre de “Efecto Domin´”. Si imaginamos una fila infinita de fichas de domin´: dispuestas vertio o calmente y suficientemente pr´ximas una cualquiera de la siguiente , entonces si el o volteamiento de la primera ficha provoca el volteamiento de la segunda ficha, por el Principio de Inducci´n...