Matematicas Discretas

Inducci¶on Matem¶atica

3.1. Inducci¶on simple

Supongamos que S(k) es una declaraci¶on v¶alida para alg¶un entero k ¸ n0

y queremos probar que S(n) es verdadero para todos los enteros n ¸ n0. El

principio de inducci¶on simple nos dice que si (1) S(n0) es verdad y (2) S(k) !

S(k +1), entonces S(n) es verdad para todos los enteros n ¸ n0. Entonces para

probar S(n) para todos los enteros n ¸ n0, necesitamos probar ¶unicamente:

1. Que S(n0) es verdad (caso base).

2. Que si S(k) es verdad (hip¶otesis de inducci¶on), entonces S(k +1) es tam-

bi¶en verdad (paso de inducci¶on).

Ejemplo 1

Dejemos que S(n) denote la aserci¶on

1 + 3 + 5 + ¢ ¢ ¢ + (2n ¡ 1) = n2

para todo n ¸ 1. Ahora, S(1) es 1 = 12, que es verdad. Podemos veri¯car

algunos m¶as:

S(2) es 1 + 3 = 22

S(3) es 1 + 3 + 5 = 32

que tambi¶en se cumplen. Ahora asumamos que para alg¶un k ¸ 1, S(k) es verdad,

esto es, S(k) : 1 + 3 + 5 + ¢ ¢ ¢ + (2k ¡ 1) = k2. Considere:

1 + 3 + 5 + ¢ ¢ ¢ + (2k ¡ 1) + (2k + 1)

y reagrupemos los t¶erminos de la siguiente forma [1 + 3 + 5 + ¢ ¢ ¢ + (2k ¡ 1)] +

(2k+1), y como S(k) es verdad. reemplazamos la expresi¶on entre corchetes porCAP¶ITULO 3. INDUCCI ¶ON MATEM¶ ATICA

k2:

= k2 + (2k + 1)

= (k + 1)2

por lo que 1+3+5+¢ ¢ ¢+(2k¡1)+(2k+1) = (k+1)2 y por lo tanto S(k+1)

es verdad. Entonces por inducci¶on simple, S(n) es verdad para todo n ¸ 1.

Ejemplo 2

Probar que 1+2+3+¢ ¢ ¢+n = n(n+1)

2 se cumple para todo n ¸ 1. Denotemos

por S(n) esta aserci¶on y probemos el caso base:

S(1) : 1 =

1(1 + 1)

2

que es verdad. Ahora consideremos 1 + 2 + 3 + ¢ ¢ ¢ + n + (n + 1), reagrupando

t¶erminos tenemos [1+2+3+¢ ¢ ¢+n]+(n+1), como S(n) es verdad, entonces

reemplazamos la expresi¶on entre corchetes por n(n+1)

2 : = n(n + 1)

2

+ (n + 1)

= n(n + 1)

2

+

2(n + 1)

2

= n(n + 1) + 2(n + 1)

2

=

(n + 2)(n + 1)

2

=

(n + 1)(n + 2)

2

por lo que S(n + 1) es verdad y se deduce que S(n) es verdad para todo n ¸ 1.

Ejemplo 3

El n¶umero de¯nido como Hn = 1

1 + 1

2 + 1

3 +¢ ¢ ¢+ 1

n; n ¸ 1 es llamado n¶umero

arm¶onico. Pruebe que para todo n ¸ 1,

Xn

k=1

Hk =(n + 1)Hn ¡ n

Dejemos que S(n) denote la declaraci¶on H1 + H2 + ¢ ¢ ¢ + Hn = (n + 1)Hn ¡ n.

El caso base S(1) es H1 = 2H1 ¡ 1, puesto que H1 es 1, S(1) es verdad. Ahora

consideremos H1+H2+¢ ¢ ¢+Hn+Hn+1, reagrupando t¶erminos tenemos [H1+

H2 +¢ ¢ ¢+Hn]+Hn+1 y puesto que S(n)

...