Upload
others
View
5
Download
0
Embed Size (px)
Citation preview
Inducción Matemática Matemáticas Discretas - p. 1/34
Matemáticas DiscretasTC1003
Inducción MatemáticaDepartamento de Matemáticas / Centro de Sistema Inteligentes
ITESM
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 2/34
Inducción Matemática: Historia
Inducción Matemática es unmétodo de prueba relativa-mente reciente: el primer usoconocido lo hizo el sacerdo-te italiano Francesco Mauroli-co (1494-1575) en su publica-ción “Arithmeticorum libri duo”(1575).
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 3/34
Inducción Matemática: Historia
En el siglo 17 tanto Piere deFermat como Blaise Pascal uti-lizaron inducción matemáticapara hacer demostraciones.
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 4/34
Inducción Matemática: Historia
En 1883 Augustus De Morganfue el primero que describió elproceso cuidadosamente y lenombró inducción matemática.
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 5/34
Inducción Matemática: Idea Intuitiva
Suponga una fila interminablede fichas de dominó.
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 5/34
Inducción Matemática: Idea Intuitiva
Suponga una fila interminablede fichas de dominó. Supon-ga que las fichas están estra-tegicamente colocadas de talforma que si cualquiera caye-ra hacia adelante tumbaría lasiguiente ficha hacia adelan-te. (Paso Inductivo) Supongatambién que la primera fichacae hacia adelante.(Base In-ductiva)¿Qué pasará con las fichas dedominó?¡Caerán todas!
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 6/34
Inducción Matemática: Formulación
Suponga que una propiedad (fórmula,desigualdad, condición etc) P(n) que está definidapara los enteros apartir de un entero fijo a (Paran = a, para n = a + 1, para n = a + 2, . . . ) Supongaque las dos siguientes afirmaciones son ciertas:■ P(a) es verdadero.■ Para cualquier entero k mayor o igual que a:
Si P(k) es cierto, entonces P(k + 1) es cierto.
Entonces la afirmación:
Para todos los enteros n ≥ a, P(n)
es verdadera.
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 7/34
Inducción Matemática: El Método
Para demostrar que es verdadera una afirmación:
Para todos los enteros n ≥ a, P(n)
Pruebe que:■ Paso 1 (Base Inductiva): P(a) es verdadero.■ Paso 2 (Paso Inductivo): Muestre que para
cualquier entero k ≥ a . . .◆ suponiendoque P(k) es verdadera (Hipótesis
inductiva)◆ entonces muestreque P(k + 1) también es
verdadera.
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 8/34
Inducción Matemática: Ejemplo 1
Suponiendo como válidas las reglas de derivación
ddx
x = 1
y que
ddx
( f (x) · g(x)) = g(x) ·ddx
f (x) + f (x) ·ddx
g(x)
Demuestre que para todo entero n ≥ 1
ddx
xn= n xn−1
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 9/34
DemostracionDe acuerdo al principio de inducción matemáticadebemos demostrar:Base inductiva:Que la afirmación es veradera para el primero deesos enteros. En este caso n = 1. La fórmula quedebemos demostrar para n = 1 queda:
ddx
x1= 1 x1−1
es decir,ddx
x = 1
pero esto es uno de los datos que tenemos en elproblema. Por tanto, la afirmación es cierta paran = 1.
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 10/34
Paso inductivo:Supongamos que para un entero k ≥ 1 cualquierase cumple:
ddx
xk= k xk−1
Mostremos que entonces se cumple:
ddx
xk+1= (k + 1) xk+1−1
= (k + 1) xk
(La igualdad anterior se debe probar) Trabajemoscon el lado izquierdo de la igualdad que queremosdemostrar y hagamos un truco matemático:
ddx
xk+1=
ddx
(
xk· x)
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 11/34
Si tomamos como f (x) = xk y como g(x) = x yutilizamos como probada al fórmula dada al iniciodel problema tenemos´:
ddx
xk+1=
ddx
(
xk· x)
= xddx
xk+ xk d
dxx
Por la hipótesis inductiva ddx xk= k xk−1, entonces
tenemos que la igualdad anterior queda:
ddx
xk+1= x
ddx
xk+ xk d
dxx = x·k xk−1
+ xk· 1
Si hacemos álgebra en el lado derechoobtenemos:
ddx
xk+1= (k + 1) xk
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 12/34
Que era la fórmula que debíamos demostrar. Portanto hemos probado que si d
dx xk= k xk−1 es
verdadera, entonces ddx xk+1
= (k + 1) xk es tambiénverdadera.Es decir, hemos probado el paso inductivo.Por haber probado la base inductiva y el pasoinductivo, el principio de inducción matemáticadice que la afirmación es cierta:
Para todo entero n ≥ 1,ddx
xn= n xn−1
.
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 13/34
Inducción Matemática: Ejemplo 2
Demuestre que para enteros n ≥ 3:
2n + 1 ≤ 2n
DemostracionDe acuerdo al principio de inducción matemáticadebemos demostrar:Base inductiva:Que la afirmación es veradera para el primero deesos enteros. En este caso n = 3. La desigualdadque debemos demostrar para n = 3 queda:
2 · 3+ 1 ≤ 23
es decir, 7 ≤ 8, pero esto es verdadero. Por tanto,la afirmación es cierta para n = 3.
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 14/34
Paso inductivo:Supongamos que para un entero k ≥ 3 cualquierase cumple:
2k + 1 ≤ 2k
Mostremos que entonces se cumple:
LHS = 2 (k + 1)+ 1 ≤ 2k+1
(La desigualdad anterior se debe probar)Trabajemos con el lado izquierdo de ladesigualdad que queremos demostrar:
LHS = 2 (k + 1)+ 1 = 2k + 1+ 2
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 15/34
Por la hipótesis inductiva 2k + 1 ≤ 2k y como parak ≥ 3, 2 ≤ 2k, lo anterior queda:
LHS = 2 (k + 1)+ 1 = 2k + 1+ 2 ≤ 2k+ 2 ≤ 2k
+ 2k
Por tanto, hemos probado que
2 (k + 1)+ 1 ≤ 2k+ 2k= 2 · 2k
= 2k+1
Esto es justo la afirmación para n = k + 1. Portanto, hemos probado el paso inductivo. Por elprincipio de inducción matemática la afirmación esverdadera:
Para cualquier entero n ≥ 3, 2n + 2 ≤ 2n
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 16/34
Note que en la demostración anterior hemoshecho uso de lo siguiente:■ Si A ≤ B, entonces A +C ≤ B +C.■ Si A ≤ B y B ≤ C, entonces A ≤ C.
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 17/34
Inducción Matemática: Ejemplo 3
Demuestre que para enteros n ≥ 4:
n2≤ 2n
DemostracionDe acuerdo al principio de inducción matemáticadebemos demostrar:Base inductiva:Que la afirmación es veradera para el primero deesos enteros. En este caso n = 4. La desigualdadque debemos demostrar para n = 4 queda:
42≤ 24
es decir, 16≤ 16, pero esto es verdadero. Portanto, la afirmación es cierta para n = 4.
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 18/34
Paso inductivo:Supongamos que para un entero k ≥ 4 cualquierase cumple:
k2≤ 2k
Mostremos que entonces se cumple:
LHS = (k + 1)2 ≤ 2k+1
(La desigualdad anterior se debe probar)Trabajemos con el lado izquierdo de ladesigualdad que queremos demostrar:
LHS = (k + 1)2 = k2+ 2k + 1
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 19/34
Por la hipótesis inductiva k2≤ 2k y como para
k ≥ 4 ≥ 3, 2k + 1 ≤ 2k, lo anterior queda:
LHS = (k + 1)2 = k2+ 2k + 1 ≤ 2k
+ 2k + 1 ≤ 2k+ 2k
Por tanto, hemos probado que
(k + 1)2 ≤ 2k+ 2k= 2 · 2k
= 2k+1
Esto es justo la afirmación para n = k + 1. Portanto, hemos probado el paso inductivo. Por elprincipio de inducción matemática la afirmación esverdadera:
Para cualquier entero n ≥ 4, n2≤ 2n
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 20/34
Inducción Matemática: Ejemplo 4
Demuestre que para enteros n ≥ 1:
1+ 2+ · · · + n =k∑
i=1
i =n(n + 1)
2
DemostracionDe acuerdo al principio de inducción matemáticadebemos demostrar:Base inductiva:Que la afirmación es veradera para el primero deesos enteros. En este caso n = 1. La igualdad quedebemos demostrar para n = 1 queda:
1∑
i=1
i = 1 =1 · (1+ 1)
2= 1
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 21/34
Paso inductivo:Supongamos que para un entero k ≥ 1 cualquierase cumple:
k∑
i=1
i =k(k + 1)
2
Mostremos que entonces se cumple:
LHS =k+1∑
i=1
i =(k + 1)(k + 1+ 1)
2=
(k + 1)(k + 2)2
(La igualdad anterior se debe probar)
LHS =k+1∑
i=1
i =
k∑
i=1
i
+ k + 1
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 22/34
Por la hipótesis inductiva∑k
i=1 i = k(k+1)2 lo anterior
queda:
LHS =k+1∑
i=1
i =
k∑
i=1
i
+ k + 1 =k(k + 1)
2+ k + 1
Haciendo álgebra tenemos:
k(k + 1)2
+ k + 1 =k(k + 1)+ 2(k + 1)
2=
(k + 1)(k + 2)2
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 23/34
Por tanto, hemos probado que
k+1∑
i=1
i =(k + 1)(k + 2)
2
Esto es justo la afirmación para n = k + 1. Portanto, hemos probado el paso inductivo. Por elprincipio de inducción matemática la afirmación esverdadera:
Para cualquier entero n ≥ 1,n∑
i=1
i =n(n + 1)
2
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 24/34
Inducción Matemática: Ejemplo 5
Suponga una sucesión de números a1, a2, a3,. . . que cumplen la siguientes reglas:■ Regla 1: a1 = 1, y■ Regla 2: an+1 = 2an + 1 para n ≥ 1.Pruebe que la fórmula para los números an paran ≥ 1 es:
an = 2n− 1
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 25/34
DemostracionDe acuerdo al principio de inducción matemáticadebemos demostrar:Base inductiva:Que la afirmación es veradera para el primero deesos enteros. En este caso n = 1. La igualdad quedebemos demostrar para n = 1 queda:
a1 = 21− 1 = 1
pero esto es verdadero por la regla 1. Por tanto,la afirmación es cierta para n = 1.
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 26/34
Paso inductivo:Supongamos que para un entero k ≥ 1 cualquierase cumple:
ak = 2k− 1
Mostremos que entonces se cumple:
ak+1 = 2k+1− 1
(La igualdad anterior se debe probar) Trabajemoscon el lado izquierdo de la igualdad que queremosdemostrar: por la regla 2:
ak+1 = 2ak + 1
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 27/34
Por la hipótesis inductiva ak = 2k− 1 lo anterior
queda:
ak+1 = 2ak + 1 = 2(2k− 1) + 1 = 2k+1
− 1
Por tanto, hemos probado que
ak+1 = 2k+1− 1
Esto es justo la afirmación para n = k + 1. Portanto, hemos probado el paso inductivo. Por elprincipio de inducción matemática la afirmación esverdadera:
Para cualquier entero n ≥ 1, an = 2n− 1
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 28/34
Inducción Matemática: Ejemplo 6
Considere el programa:SD(A,n,x)variable A array of floatvariable n integervariable x floatif (n = 1) then[a] return(A[1])else[b] return(A[n] + x*SD(A,n-1,x))end ifend proc
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 29/34
Afirmación para n ≥ 1:
SD(A, n, x) =∑n
i=1 A[i]xn−i
= A[n] + A[n − 1] x1+ · · · + A[1] xn−1
y su ejecución se realiza con 2(n − 1) FLOPs.
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 30/34
DemostracionBase inductiva:Debemos demostrar que para n = 1 el programaregresa :
1∑
i=1
A[i] x1−i= A[1] x1−1
= A[1].
Pero esto es verdadero, pues el programa paran = 1 sale por la línea [a] entregando esto.Además, como no realiza ninguna operación depunto flotante se coincide con la fórmula para elnúmero de FLOPs invertidos: 2 (1− 1) = 0. Portanto, la afirmación es cierta para n = 1.
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 31/34
Paso inductivo:Supongamos que para un entero k ≥ 1 cualquierase cumple:
SD(A, k, x) =k∑
i=1
A[i]xk−i
Y que lo hace con 2(k − 1) FLOPs. Mostremos queentonces se cumple:
SD(A, k + 1, x) =k+1∑
i=1
A[i]xk+1−i
y que lo hace en 2(k + 1− 1) = 2k FLOPs.
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 32/34
Revisemos la ejecución del programa paran = k + 1: Como k ≥ 1 entonces k + 1 , 1. Por lotanto, el programa ejecuta la línea [b] entregando:
SD(A, k + 1, x) = A[n] + x × SD(A, k, x)
Por la hipótesis inductiva:
SD(A, k + 1, x) = A[n] + x ×k∑
i=1
A[i]xk−i
Por propiedades matemáticas lo anterior queda:
SD(A, k + 1, x) = A[n] +k∑
i=1
A[i]xk+1−i=
k+1∑
i=1
A[i]xk+1−i
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 33/34
Además, haciendo en conteo de las operacionesrealizadas■ la llamada recursiva requerirá 2(k − 1) FLOPs, y■ la línea [b] requerirá aún dos FLOPs más: una
suma y una multiplicación.Es decir, que el número de operacionesinvolucradas serán
2(k − 1)+ 2 = 2k
Esto es exactamente lo que se quería demostrar.
HistoriaHistoriaHistoriaIdeaFormulacionMetodoEjemplo 1Ejemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6
Inducción Matemática Matemáticas Discretas - p. 34/34
Por tanto, hemos probado que bajo la hipótesisinductiva, validez de lo afirmado para n = k, elprograma ejecutado para n = k + 1 entrega
SD(A, k + 1, x) =k+1∑
i=1
A[i]xk+1−i
y lo hace en 2(k + 1− 1) FLOPs. Lo que esexactamente la afirmación para n = k + 1. Portanto, hemos probado el paso inductivo. Por elprincipio de inducción matemática la afirmación esverdadera para enteros n ≥ 1.