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),

...