Matematicas Discretas
Enviado por ZoneCero • 31 de Enero de 2012 • 462 Palabras (2 Páginas) • 978 Visitas
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),
...