Induccion Completa

Cap´
ıtulo 1

´
LA DEMOSTRACION
´
MATEMATICA.
´
DEMOSTRACION POR
´
INDUCCION Y FORMA
FUERTE DEL PRINCIPIO
´
DE INDUCCION (O
´
INDUCCION
COMPLETA)
1.1.

M´todo de demostraci´n por inducci´n
e
o
o

Se trata de demostrar una proposici´n, P , del tipo ∀ n ∈ N se verifica P (n),
o
siendo P (n) una propiedad que se refiere al n´mero natural n.
u
Se procede como sigue:
1. Secomprueba que P (1) es cierta, es decir la proposici´n se verifica cuando
o
n = 1.
2. Se demuestra que si P (h) es cierta entonces P (h + 1) es cierta tambi´n,
e
es decir, que si se verifica la proposici´n para un n´mero h, a esto es lo
o
u
que llamamos hip´tesis de inducci´n (H.I.), tambi´n se verifica para el
o
o
e
siguiente (h + 1), a esto lo llamamos, tesis de inducci´n (T.I.) .
o
1Es claro que si hemos conseguido 1. y 2. entonces P (n) es cierta para cada nn
(si es cierta P (1), entonces por 2., es cierta P (2), y entonces, por 2., es cierta
P (3),...
Ejemplo 1.1.1. Demostrar por inducci´n la siguiente igualdad:
o
n

k2 =

n(n+1)(2n+1)
6

k=1

1. Lo podemos escribir como
12 + 22 + 32 + . . . + (n − 1)2 + n2 =

n(n+1)(2n+1)
6

Comprobamos si P (1) escierto. P (1) es
12 =

1(1+1)(2,1+1)
6

que resulta cierto.
2. Tenemos que demostrar que si se verifica P (h), es decir suponiendo que
12 + 22 + 32 + . . . + (h − 1)2 + h2 =

h(h+1)(2h+1)
6

entonces veamos si se cumple P (h + 1) es decir
12 + 22 + 32 + . . . + (h − 1)2 + h2 + (h + 1)2 =

(h+1)((h+1)+1)(2(h+1)+1)
6

Entonces:
12 +22 +32 +. . .+(h−1)2 +h2 +(h+1)2 = (aplico laH.I.) =

h(h+1)(2h+1)
+(h+1)2
6

Pero esto se reduce a ver, con pocas cuentas, que:
(h + 1)((h + 1) + 1)(2(h + 1) + 1) + 1) − [h(h + 1)(2h + 1) + 6(h + 1)2 ] = 0

1.2.

Forma fuerte del principio de inducci´n
o

Se llama as´ porque la hip´tesis es algo m´s fuerte. En el paso de k a k + 1
ı
o
a
debemos suponer que la afirmaci´n no solo es cierta para k sino que la afirmaci´n
o
o
escierta hasta k .
2

Ejemplo 1.2.1. Haciendo uso del PIC (principio de inducci´n completa o
o
fuerte) demostrar que cualquier n´mero natural mayor que 1 se puede escribir
u
como producto de n´meros primos.
u
Ahora como n > 1, nuestro P (1) es verificar que la propiedad se cumple para
n = 2, lo cual es obvio por ser 2 primo.
Ahora distinguimos dos casos:
Si n es primo, la propiedad estrivial, pues descompone el mismo en factores
primos.
Si n no es primo, entonces podemos descomponer n como n = k.l siendo
2 ≤ k, l < n. Ahora aplicamos la H.I. del principio de inducci´n completa que
o
nos dice que todo n´mero natural menor que n se puede descomponer en facu
tores primos. Por tanto k y l descomponen en factores primos, y as´ n tambi´n
ı
e
descompone en factores primos.3

Cap´
ıtulo 2

´
ANALISIS
COMBINATORIO
2.1.

Introducci´n
o

Regla de la Suma.- Si un objeto .A”se puede elegir de mm maneras distintas y el objeto ”B”de n, entonces .A o B”se pueden elegir de m + n maneras.
Regla del Producto.- Si un objeto .A”se puede elegir de m maneras distintas y para cada una de ellas podemos elegir ”B”de n maneras, entonces .A y
B”se pueden elegir, en eseorden, de m.n maneras distintas.

Proposici´n 2.1.1. Pares ordenados: Con m elementos diferentes entre
o
s´ {a1 , . . . , am } y n elementos tambi´n diferentes entre si {b1 , . . . , bn } es posible
ı
e
formas mn pares ordenados (ai , bj ) conteniendo un elemento de cada grupo.
´
DEMOSTRACION.Agrupando todos los pares en una tabla con m filas y n columnas de modo
que (ai , bj ) se coloqueen la fija i, columna j, resulta que toda la tabla queda
completamente ocupada y cada par s´lo aparece una vez, de donde se deduce que
o
hay un total de mn pares posibles.
4

Remark 2.1.1. Observa que este ultimo resultado nos est´ dando el n´mero de
´
a
u
elementos que contine el producto cartesiano A × B de dos conjuntos con m y
n elementos respectivamente:
A × B = {a1 , a2 , . ....