Induccion Matematica

INDUCCI´ON MATEM´ATICA

EDUARDO S´AEZ , IV´AN SZ´ANT´ O DEPARTAMENTO DE MATEM´ATICA UNIVERSIDAD TECNICA FEDERICO SANTA MARIA

1. INTRODUCCI´ON

El m´etodo deductivo, muy usado en matema´tica, obedece a la siguiente idea: “ A partir de un cierto conjuntos de axiomas aceptados sin demostracio´n y de reglas lo´gicas no contradictorias, se deducen otros enunciados llamados teoremas combi- nando los axiomas y respetando en cada etapa las reglas lo´gicas”. Otro m´etodo para demostrar resultados generales que dependen en algu´n sentido de los nu´meros naturales es conocido con el nombre de Induccio´n Mat´ematica . Esta dependencia de los nu´meros naturales significa: se sabe que una determinada afirmacio´n es verdadera para algunos casos particulares y surge la pregunta. ¿ Dicha afirmacio´n sigue siendo verdadera para los infinitos nu´meros naturales restante ?. Existen muchas afirmaciones que so´lo son va´lidas para un nu´mero finito de casos y en consecuencia son falsas para un nu´mero infinitos de situaciones. Sin embargo, podemos encontrar proposiciones (afirmaciones) que son verdaderas so´lo a partir de un cierto nu´mero natural n0, de ser asi, la t´ecnica que se desarrollaremos se llama Induccio´n Incompleta. Para demostrar que una proposicio´n p(n) ,∀n ∈ M ⊆ N, 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 Induccio´n Completa. Si se requiere demostrar la falsedad de una cierta proposicio´n p(n),∀n ∈ M ⊆ N,es suficiente indicar un elemento particular m ∈ M de manera que p(m) sea falsa.( Construccio´n de un contra ejemplo). Ejemplo 1. ∀n ∈N,n2 −3n−1 < 0 Es fa´cil probar que esta desigualdad es verdadera para n = 1,2,3. Sin embargo, para n = 4 no se cumple ya que 42 −3·4−1 = 3 > 0. No´tese que este ejemplo sencillo muestra que una proposicio´n puede ser verdadera para los primeros nu´meros naturales, sin embargo, es falsa , para nu´meros naturales ma´s grandes.

Copyright 2004, Derechos reservados, no ´esta permitido la reproduccio´n parcial o total de este material sin el permiso de sus autores . 1

2 INDUCCI´ON MATEM´ATICA

Otros ejemplos: Ejemplo 2. ∀n ∈N, (2n−1)(2n + 1)(2n + 3), es divisible por 5. Es fa´cil probar que esta proposicio´n es verdadera para n = 1,2,3. Sin embargo, 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 cuadra´tico p(n) = n2 +n+41 y determinemos su valor para ciertos n ∈N n : 1 2 3 4 5 6 7 8 n2 + n + 41 : 43 47 53 61 71 83 97 113 No´tese que todos los nu´meros que se obtienen son primos. Se podr´ıa esperar que este polinomio cuadra´tico continua generando nu´meros primos. Desafortunadamente no es asi, para n = 40, se tiene 1681 = 412, que no es un nu´mero primo, luego la proposicio´n que ∀n ∈N, n2 + n + 41 es un nu´mero primo resulta falsa.

2. Principio de induccio´n Matem´atica

Una proposicio´n p(n) es verdadera para todos los valores de la variable n si se cumplen las siguientes condiciones :

Paso 1.- La proposicio´n p(n) es verdadera para n = 1 , o bien, p(1) es verdadera. Paso 2.- Hipo´tesis de Induccio´n . Se supone que p(k) es verdadera , donde k es un nu´mero natural cualesquiera. Paso 3.- T´esis de Induccio´n. Se demuestra que p(k + 1) es verdadera, o bien, p(k) verdadera ⇒p(k + 1) verdadera. La t´ecnica de Induccio´n Matema´tica consiste en los tres pasos anteriores. Si se necesita demostrar la validez de una proposicio´n p(n) para todos los valores naturales n, entonces es suficiente que se cumplan: Paso 1, Paso 2 y Paso 3 . Comentario: Intuitivamente la idea anterior se conoce con el nombre de “Efecto Domino´”. Si imaginamos una fila infinita de fichas de domino´: dispuestas verti- calmente y suficientemente pro´ximas una cualquiera de la siguiente , entonces si el volteamiento de la primera ficha provoca el volteamiento de la segunda ficha, por el Principio de Induccio´n Matema´tica la fila completa es volteada. Existen dos variantes u´tiles sobre el Principio de Induccio´n Matema´tica que deben ser considerados . En la primera variante, la proposicio´n

...