numeros naturales

Numeros naturales, principio de inducci´n
´
o

1. Conjuntos inductivos.
Denotaremos por IN al conjunto de n´meros naturales, IN = {1, 2, 3, 4, 5, 6, . . .}, cuyos
u
elementos son suma de un n´mero finito de unos. Recordemos que IN es cerrado para la
u
suma y el producto (la suma y el producto de n´meros naturales son n´meros naturales),
u
u
7
pero no lo es para la resta o la divisi´n(4 − 9 ∈ IN y 5 ∈ IN).
o
/
/
Diremos que un subconjunto S de IR es inductivo si se satisfacen:
i) 1 ∈ S
ii) k ∈ S =⇒ k + 1 ∈ S
Ejemplos.
i) IR, IR>0 y IR≥1 son inductivos.
ii) IR −3}
Z
Notemos que si S ⊆ IR es un conjunto inductivo entonces 1 ∈ S por i). Pero esto implica
que 2 ∈ S por ii) y luego 3 ∈ S nuevamente por ii), etc. Luego, IN ⊆ S . Por lo tanto,
IN es un conjunto inductivoque est´ contenido en todos los conjuntos inductivos. Si
a
consideramos el orden en los conjuntos dado por ⊆, esto puede resumirse en la forma: IN
es un conjunto inductivo que es menor que todo otro conjunto inductivo.
Supongamos ahora que H es un subconjunto de IR que tiene esta propiedad, es decir, H es
inductivo y H est´ contenido en todos los conjuntos inductivos. Entonces debe ser H =IN
a
(¿porque?) y esto significa que IN es el unico conjunto inductivo que est´ contenido en
´
a
todos los conjuntos inductivos. Si quisi´ramos dar una definici´n rigurosa del conjunto de
e
o
n´meros naturales podr´
u
ıamos definirlo como el unico conjunto inductivo que est´ contenido
´
a
en todos los conjuntos inductivos, es decir, la intersecci´n de todos los subconjuntos de IR
o
queson inductivos.

1

ALGEBRA I

N´ meros naturales
u

Observaci´n. De lo anterior se deduce que si H es un subconjunto de IN que satisface
o
i) 1 ∈ H
ii) k ∈ H =⇒ k + 1 ∈ H
entonces H = IN.
2. Principio de inducci´n.
o
Sea P (n) una funci´n proposicional predicable sobre IN. Si valen
o
1) P (1) es verdadera
2) P (k ) =⇒ P (k + 1), para todo k ∈ IN
entonces P (n) es verdaderapara todo n ∈ IN.
Demostraci´n: Sea H = {h ∈ IN / P (h) es verdadera}. Entonces H es un subconjunto de
o
IN que satisface
i) 1 ∈ H
ii) k ∈ H =⇒ k + 1 ∈ H
Luego, por la observaci´n anterior, H = IN y por lo tanto P (n) es verdadera para todo
o
n ∈ IN.
Resumiendo, el principio de inducci´n dice que para probar que P (n) es verdadera para
o
todo n ∈ IN alcanza con probar que valen 1) y 2).Ejemplos.
a) P (n) : n + 3 ≥ n + 7 satisface 2) pues k + 3 ≥ k + 7 =⇒ k + 1 + 3 ≥ k + 1 + 7 pero sin
embargo P (n) no es verdadera para todo n ∈ IN. Lo que sucede en este caso es que P (1)
es falsa. Esto muestra que es necesario probar que P (1) es verdadera.
b) P (n) : n ≤ 7 satisface 1) pero sin embargo P (n) no es verdadera para todo n ∈ IN. Lo
que sucede es que no se satisface 2) pues P(7) no implica P (8) ya que P (7) es verdadera
y P (8) es falsa. Esto muestra que es necesario probar que P (k ) =⇒ P (k + 1).
c) P (n) : 5n ≥ 2n + 3n . Veamos que en este caso valen 1) y 2) y por lo tanto P (n) es
verdadera ∀ n ∈ IN. Es claro que P (1) : 5 ≥ 2 + 3 es verdadera. Sea k ∈ IN. Veamos ahora
que P (k ) =⇒ P (k + 1), es decir, 5k ≥ 2k + 3k =⇒ 5k+1 ≥ 2k+1 + 3k+1
Supongamos que 5k ≥2k + 3k (esta es la hip´tesis inductiva a la que abreviaremos con
o
k+1
k+1
k+1
HI). Debemos probar que 5
≥2
+3
5k+1 = 5.5k

≥

5.(2k + 3k ) = 5.2k + 5.3k

por HI

≥
5≥2

2.2k + 5.3k

≥

2.2k + 3.3k = 2k+1 + 3k+1

5≥ 3

Luego, 5n ≥ 2n + 3n ∀ n ∈ IN.
d) P (n) : n5 ≥ n4 . Si bien puede demostrarse que P (n) es verdadera ∀ n ∈ IN utilizando
el principio de inducci´n,notemos que la siguiente demostraci´n es mucho m´s corta y
o
o
a
sencilla: dado n ∈ IN

2

ALGEBRA I

N´ meros naturales
u

n5 ≥ n4 ⇐⇒

n5
≥ 1 ⇐⇒ n ≥ 1
n4

Como n ≥ 1 pues n ∈ IN entonces n5 ≥ n4 .
Moraleja: El principio de inducci´n es una herramienta util pero no siempre es la manera
o
´
m´s conveniente de demostrar que P (n) es verdadera ∀ n ∈ IN.
a
e) Sea (an )n∈IN la...