Principio De Inducci N Fuerte

Cap´ıtulo 2: Inducci´on y recursi´on
Clase 2: El principio de Inducci´on Fuerte
Matem´
atica Discreta - CC3101
Profesor: Pablo Barcel´o

P. Barcel´
o

–

Matem´
atica Discreta - Cap. 2: Inducci´
on y Recursi´
on

1 / 20

Motivaci´on

En esta clase presentamos un nuevo principio de inducci´on,
llamado de inducci´on fuerte, que puede ser utilizado en casos
cuando la inducci´on tradicional esdif´ıcil de aplicar.

P. Barcel´
o

–

Matem´
atica Discreta - Cap. 2: Inducci´
on y Recursi´
on

2 / 20

Motivaci´on

En esta clase presentamos un nuevo principio de inducci´on,
llamado de inducci´on fuerte, que puede ser utilizado en casos
cuando la inducci´on tradicional es dif´ıcil de aplicar.
Principio de Inducci´on Fuerte: Una propiedad P es cierta de todos
los n´
umeros naturales si:

P. Barcel´o

◮

P(1) es cierto, y

◮

para todo n´
umero natural n, si P(j) es cierto para todo
j ∈ [1, n], entonces P(n + 1) tambi´en es cierto.

–

Matem´
atica Discreta - Cap. 2: Inducci´
on y Recursi´
on

2 / 20

Inducci´on fuerte vs Inducci´on usual

Claramente, la inducci´
on fuerte nos da m´
as flexibilidad para probar
algo que la inducci´on tradicional:
◮

Podemos utilizar cualquier hip´
otesisinductiva previa;

◮

si algo se puede demostrar mediante inducci´
on usual tambi´en
se puede demostrar mediante inducci´
on fuerte.

Mostraremos a continuaci´
on c´
omo la inducci´
on fuerte puede
simplificarnos la vida en algunos casos.

P. Barcel´
o

–

Matem´
atica Discreta - Cap. 2: Inducci´
on y Recursi´
on

3 / 20

Ejemplo de aplicaci´on de Inducci´on Fuerte

Ejercicio: Demuestre usandoinducci´
on fuerte que todo entero
n > 1 puede ser escrito como un producto de n´
umeros primos. (Y
preg´
untese luego si esto puede ser demostrado usando inducci´on
usual).
(El caso base es trivial. A continuaci´
on probaremos el caso
inductivo).

P. Barcel´
o

–

Matem´
atica Discreta - Cap. 2: Inducci´
on y Recursi´
on

4 / 20

Ejemplo de aplicaci´on de Inducci´on Fuerte
Caso inductivo: Considereel entero k + 1, y asuma por hip´
otesis
inductiva que todo entero j ∈ [2, k] puede ser escrito como un
producto de primos.

P. Barcel´
o

–

Matem´
atica Discreta - Cap. 2: Inducci´
on y Recursi´
on

5 / 20

Ejemplo de aplicaci´on de Inducci´on Fuerte
Caso inductivo: Considere el entero k + 1, y asuma por hip´
otesis
inductiva que todo entero j ∈ [2, k] puede ser escrito como un
producto deprimos.
Consideramos dos casos:
◮

k + 1 es primo: Trivial.

◮

k + 1 no es primo: Existen dos enteros j, ℓ ∈ [2, k] tal que
k + 1 = jℓ.
Por hip´
otesis inductiva, j y ℓ pueden ser escritos como
productos de primos.
Concluimos que k + 1 puede ser escrito como producto de
primos.

P. Barcel´
o

–

Matem´
atica Discreta - Cap. 2: Inducci´
on y Recursi´
on

5 / 20

Otras formas de Inducci´on Fuerte

Aveces es conveniente usar una forma de inducci´
on en que el caso
inductivo s´olo aplica a enteros mayores que un entero dado:
Sea b un entero, y j un entero positivo. Entonces, una propiedad P
de los n´
umeros naturales es cierta para todo entero n ≥ b si:

P. Barcel´
o

◮

P(b), P(b + 1), . . . , P(b + j) son ciertas; y

◮

para todo k ≥ b + j, si P(ℓ) es cierto para cada ℓ ∈ [b, k],
entonces P(k+ 1) es cierto.

–

Matem´
atica Discreta - Cap. 2: Inducci´
on y Recursi´
on

6 / 20

Otras formas de Inducci´on Fuerte

A veces es conveniente usar una forma de inducci´
on en que el caso
inductivo s´olo aplica a enteros mayores que un entero dado:
Sea b un entero, y j un entero positivo. Entonces, una propiedad P
de los n´
umeros naturales es cierta para todo entero n ≥ b si:
◮

P(b), P(b +1), . . . , P(b + j) son ciertas; y

◮

para todo k ≥ b + j, si P(ℓ) es cierto para cada ℓ ∈ [b, k],
entonces P(k + 1) es cierto.

A continuaci´
on veremos un ejemplo de c´
omo aplicar este m´etodo.

P. Barcel´
o

–

Matem´
atica Discreta - Cap. 2: Inducci´
on y Recursi´
on

6 / 20

Un ejemplo de esta forma de inducci´on
Ejercicio: Demuestre que cualquier cantidad de plata mayor o igual
a 12...