matematicas

Inducci´n matem´tica
o
a
A menudo deseamos probar proposiciones de la forma ∀ n ∈ N, p(n). Por
ejemplo:
(1) ∀ n ∈ N, 1 + 2 + 3 + · · · + n = 1 n(n + 1).
2
(2) ∀ n ∈ N, (n − 2)2 = n2 − 2n + 4.
(3) ∀ n ∈ N, n par implica n2 par.
Proposiciones (2) y (3) se pueden probar usando la t´cnica de variable
e
“fija pero arbitraria”que vimos anteriormente (ejercicio para el lector), pero
esto nofunciona para la proposici´n (1).
o
Una raz´n para esta dificultad es que el lado izquierdo de la igualdad no
o
est´ en forma cerrada y, por lo tanto, no se puede manipular algebraicamente.
a
En efecto, a´n para entender que significa la expresi´n del lado izquierdo
u
o
tenemos que recurrir a una propiedad de los n´meros naturales: Dado un
u
n´mero natural k existe un “siguiente”n´meronatural, que se llama k + 1.
u
u
As´ podr´
ı,
ıamos esperar que una demostraci´n de (1) involucre esta pro o
piedad “siguiente”de los n´meros naturales.
u
En efecto, la propiedad de N a que nos referimos es uno de los cinco
postulados de Peano para los n´meros naturales. El lector interesado en los
u
fundamentos axiom´ticos de N puede consultar la bibliograf´ E. Landau,
a
ıa:Foundations of Analysis, Chelsea, New York, 1951.
Axioma 1 (Principio de inducci´n matem´tica) Sea S ⊆ N con la propiedad
o
a
que:
a) 1 ∈ S.
b) ∀ k ∈ R, k ∈ S −→ k + 1 ∈ S.
Entonces S = N.
podemos usar el principio de inducci´n matem´tica para probar una proposio
a
1

ci´n de la forma ∀ n ∈ N, p(n) haciendo
o
S = {n ∈ N : p(n) es verdadera }.
As´ consideramos que p(1) es verdadero (1 ∈ S) yp(k) −→ p(k + 1) (k ∈
ı,
S −→ k + 1 ∈ S) entonces S = N ´
o
∀ n ∈ N , p(n).
En consecuencia, demostraciones usando el principio de inducci´n matem´tica
o
a
toman la siguiente forma:
a) Mostrar que p(1) es verdadero.
b) Mostrar que p(k) −→ p(k + 1).
1
Ejemplo: Demostrar que ∀ n ∈ N, 1 + 2 + 3 + · · · + n = 2 n(n + 1).

Aqu´ p(n) es “1 + 2 + 3 + · · · + n = 1 n(n + 1)”. As´ p(1) es
ıı
2
1
“1 = (1)(1 + 1)”
2
que es claramente verdadero.
Para completar la inducci´n se debe demostrar que una cierta implicaci´n
o
o
(∀ k, p(k) −→ p(k + 1)) es verdadera.
Usaremos nuestro m´todo directo de demostraci´n para esta proposici´n:
e
o
o
Elegimos un n´mero natural k fijo pero arbitrario, asumimos que la hip´tesis
u
o
(p(k)) es verdadera y deducimos la validez de laconclusi´n(p(k + 1)).
o
Para comenzar, sea k ∈ N. Supongamos que p(k) es verdadero, esto es,
1
1 + 2 + 3 + · · · + k = k(k + 1).
2
Entonces,
1
k(k + 1) + (k + 1)
2
1
= (k + 1)( k + 1)
2
1
(k + 1)(k + 2).
=
2

1 + 2 + 3 + ··· + k + k + 1 =

2

As´ p(k + 1) es verdadero, lo que completa la demostraci´n.
ı,
o
Ejemplos
a) Si x ≥ 0 entonces ∀ n ∈ N, (1 + x)n ≥ 1 + xn .
Demostraci´npor inducci´n: Cuando n = 1 se tiene 1 + x ≥ 1 + x lo cual
o
o
es verdadero.
Supongamos que x ≥ 0, k ∈ 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´n.
o
b) ∀ n ∈ N, n2 ≤ n.
Cuando n = 1 se tiene 12 ≤ 1 lo cual es verdadero.
Supongamos que k ∈ N y k 2 ≤ k. Entonces
(k + 1)2 ≤ k + 1implica
k 2 + 2k + 1 ≤ k + 1
´
o
k 2 + 2k ≤ k
lo cual implica
k 2 ≤ k,
que es nuestra hip´tesis original, supuesta verdadera. Esto completa la deo
mostraci´n.
o
3

Observe lo sorprendente que resulta la proposici´n anterior.
o
Ciertamente el resultado anterior es falso, de manera que debe existir
alg´n error en la demostraci´n.
u
o
El ejemplo b) muestra un error com´n que secomete al empezar a manejar
u
el m´todo de inducci´n.
e
o
Un an´lisis muestra que en la prueba anterior se asume la conclusi´n y
a
o
entonces se obtuvo la hip´tesis, una forma de demostraci´n que nunca es
o
o
v´lida.
a
Si todas las las implicaciones pudiesen ser revertidas, se podr´ construir
ıa
una demostraci´n v´lida invirtiendo el orden de los pasos, pero en este caso
o a
el...