Tuti

http://www.youtube.com/watch?v=mwYudS5KN1k
Inducci´on matem´atica
A menudo deseamos probar proposiciones de la forma 8 n 2 N, p(n). Por
ejemplo:
(1) 8 n 2 N, 1 + 2 + 3 + ¢ ¢ ¢ + n = 1
2n(n + 1).
(2) 8 n 2 N, (n ¡ 2)2 = n2 ¡ 2n + 4.
(3) 8 n 2 N, n par implica n2 par.
Proposiciones (2) y (3) se pueden probar usando la t´ecnica de variable
“fija pero arbitraria”que vimos anteriormente(ejercicio para el lector), pero
esto no funciona para la proposici´on (1).
Una raz´on para esta dificultad es que el lado izquierdo de la igualdad no
est´a en forma cerrada y, por lo tanto, no se puede manipular algebraicamente.
En efecto, a´un para entender que significa la expresi´on del lado izquierdo
tenemos que recurrir a una propiedad de los n´umeros naturales: Dado un
n´umero natural kexiste un “siguiente”n´umero natural, que se llama k + 1.
As´ı, podr´ıamos esperar que una demostraci´on de (1) involucre esta pro -
piedad “siguiente”de los n´umeros naturales.
En efecto, la propiedad de N a que nos referimos es uno de los cinco
postulados de Peano para los n´umeros naturales. El lector interesado en los
fundamentos axiom´aticos de N puede consultar la bibliograf´ıa: E.Landau,
Foundations of Analysis, Chelsea, New York, 1951.
Axioma 1 (Principio de inducci´on matem´atica) Sea S µ N con la propiedad
que:
a) 1 2 S.
b) 8 k 2 R, k 2 S ¡! k + 1 2 S.
Entonces S = N.
podemos usar el principio de inducci´on matem´atica para probar una proposi-
1
ci´on de la forma 8 n 2 N, p(n) haciendo
S = fn 2 N : p(n) es verdadera g:
As´ı, consideramos que p(1) es verdadero (1 2S) y p(k) ¡! p(k + 1) (k 2
S ¡! k + 1 2 S) entonces S = N ´o
8 n 2 N , p(n):
En consecuencia, demostraciones usando el principio de inducci´on matem´atica
toman la siguiente forma:
a) Mostrar que p(1) es verdadero.
b) Mostrar que p(k) ¡! p(k + 1).
Ejemplo: Demostrar que 8 n 2 N, 1 + 2 + 3 + ¢ ¢ ¢ + n = 1
2n(n + 1).
Aqu´ı p(n) es “1 + 2 + 3 + ¢ ¢ ¢ + n = 1
2n(n + 1)”. As´ı p(1) es
“1 =1
2
(1)(1 + 1)”
que es claramente verdadero.
Para completar la inducci´on se debe demostrar que una cierta implicaci´on
(8 k, p(k) ¡! p(k + 1)) es verdadera.
Usaremos nuestro m´etodo directo de demostraci´on para esta proposici´on:
Elegimos un n´umero natural k fijo pero arbitrario, asumimos que la hip´otesis
(p(k)) es verdadera y deducimos la validez de la conclusi´on(p(k + 1)).
Paracomenzar, sea k 2 N. Supongamos que p(k) es verdadero, esto es,
1 + 2 + 3 + ¢ ¢ ¢ + k =
1
2
k(k + 1):
Entonces,
1 + 2 + 3 + ¢ ¢ ¢ + k + k + 1 =
1
2
k(k + 1) + (k + 1)
= (k + 1)(
1
2
k + 1)
=
1
2
(k + 1)(k + 2):
2
As´ı, p(k + 1) es verdadero, lo que completa la demostraci´on.
Ejemplos
a) Si x ¸ 0 entonces 8 n 2 N, (1 + x)n ¸ 1 + xn.
Demostraci´on por inducci´on: Cuando n = 1 setiene 1+x ¸ 1+x lo cual
es verdadero.
Supongamos que x ¸ 0, k 2 N y (1 + x)k ¸ 1 + xk. Entonces
(1 + x)k+1 = (1 + x)k(1 + x)
¸ (1 + xk)(1 + x)
= 1 + xk+1 + x + xk
¸ 1 + xk+1;
lo que completa la demostraci´on.
b) 8 n 2 N, n2 · n.
Cuando n = 1 se tiene 12 · 1 lo cual es verdadero.
Supongamos que k 2 N y k2 · k. Entonces
(k + 1)2 · k + 1
implica
k2 + 2k + 1 · k + 1
´o
k2 + 2k · k
locual implica
k2 · k;
que es nuestra hip´otesis original, supuesta verdadera. Esto completa la demostraci
´on.
3
Observe lo sorprendente que resulta la proposici´on anterior.
Ciertamente el resultado anterior es falso, de manera que debe existir
alg´un error en la demostraci´on.
El ejemplo b) muestra un error com´un que se comete al empezar a manejar
el m´etodo de inducci´on.
Un an´alisismuestra que en la prueba anterior se asume la conclusi´on y
entonces se obtuvo la hip´otesis, una forma de demostraci´on que nunca es
v´alida.
Si todas las las implicaciones pudiesen ser revertidas, se podr´ıa construir
una demostraci´on v´alida invirtiendo el orden de los pasos, pero en este caso
el ´ultimo paso no puede ser invertido (k2 · k no implica k2 + 2k · k).
El punto es: Mientras...