Inducción Matemática ´ Departamento de Matematicas

´ Matematica– ´ Induccion p. 1/31

Inducción Matemática: Historia

Inducción Matemática es un método de prueba relativamente reciente:

´ Matematica– ´ Induccion p. 2/31

Inducción Matemática: Historia

Inducción Matemática es un método de prueba relativamente reciente: el primer uso conocido lo hizo el sacerdote italiano Francesco Maurolico (1494-1575) en su publicación “Arithmeticorum libri duo” (1575).

´ Matematica– ´ Induccion p. 2/31

Inducción Matemática: Historia

Inducción Matemática es un método de prueba relativamente reciente: el primer uso conocido lo hizo el sacerdote italiano Francesco Maurolico (1494-1575) en su publicación “Arithmeticorum libri duo” (1575). En el siglo 17 tanto Piere de Fermat como Blaise Pascal utilizaron esta técnica.

´ Matematica– ´ Induccion p. 2/31

Inducción Matemática: Historia

Inducción Matemática es un método de prueba relativamente reciente: el primer uso conocido lo hizo el sacerdote italiano Francesco Maurolico (1494-1575) en su publicación “Arithmeticorum libri duo” (1575). En el siglo 17 tanto Piere de Fermat como Blaise Pascal utilizaron esta técnica. En 1883 Augustus De Morgan fue el primero que describió el proceso cuidadosamente y le nombró inducción matemática.

´ Matematica– ´ Induccion p. 2/31

Inducción Matemática: Idea Intuitiva

Suponga una fila interminable de fichas de dominó.

´ Matematica– ´ Induccion p. 3/31

Inducción Matemática: Idea Intuitiva

Suponga una fila interminable de fichas de dominó. Suponga que las fichas están estrategicamente colocadas de tal forma que si cualquiera cayera hacia adelante tumbaría la siguiente ficha hacia adelante. (Paso Inductivo)

´ Matematica– ´ Induccion p. 3/31

Inducción Matemática: Idea Intuitiva

Suponga una fila interminable de fichas de dominó. Suponga que las fichas están estrategicamente colocadas de tal forma que si cualquiera cayera hacia adelante tumbaría la siguiente ficha hacia adelante. (Paso Inductivo) Suponga también que la primera ficha cae hacia adelante.(Base Inductiva)

´ Matematica– ´ Induccion p. 3/31

Inducción Matemática: Idea Intuitiva

Suponga una fila interminable de fichas de dominó. Suponga que las fichas están estrategicamente colocadas de tal forma que si cualquiera cayera hacia adelante tumbaría la siguiente ficha hacia adelante. (Paso Inductivo) Suponga también que la primera ficha cae hacia adelante.(Base Inductiva) ¿Qué pasará con las fichas de dominó?

´ Matematica– ´ Induccion p. 3/31

Inducción Matemática: Idea Intuitiva

Suponga una fila interminable de fichas de dominó. Suponga que las fichas están estrategicamente colocadas de tal forma que si cualquiera cayera hacia adelante tumbaría la siguiente ficha hacia adelante. (Paso Inductivo) Suponga también que la primera ficha cae hacia adelante.(Base Inductiva) ¿Qué pasará con las fichas de dominó? ¡Caerán todas!

´ Matematica– ´ Induccion p. 3/31

Inducción Matemática: Formulación

Suponga que una propiedad (fórmula, desigualdad, condición etc) P (n) que está definida para los enteros apartir de un entero fijo a (Para n = a, para n = a + 1, para n = a + 2, . . . )

´ Matematica– ´ Induccion p. 4/31

Inducción Matemática: Formulación

Suponga que una propiedad (fórmula, desigualdad, condición etc) P (n) que está definida para los enteros apartir de un entero fijo a (Para n = a, para n = a + 1, para n = a + 2, . . . ) Suponga que las dos siguientes afirmaciones son ciertas:

´ Matematica– ´ Induccion p. 4/31

Inducción Matemática: Formulación

Suponga que una propiedad (fórmula, desigualdad, condición etc) P (n) que está definida para los enteros apartir de un entero fijo a (Para n = a, para n = a + 1, para n = a + 2, . . . ) Suponga que las dos siguientes afirmaciones son ciertas: P (a) es verdadero.

´ Matematica– ´ Induccion p. 4/31

Inducción Matemática: Formulación

Suponga que una propiedad (fórmula, desigualdad, condición etc) P (n) que está definida para los enteros apartir de un entero fijo a (Para n = a, para n = a + 1, para n = a + 2, . . . ) Suponga que 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.

´ Matematica– ´ Induccion p. 4/31

Inducción Matemática: Formulación

Suponga que una propiedad (fórmula, desigualdad, condición etc) P (n) que está definida para los enteros apartir de un entero fijo a (Para n = a, para n = a + 1, para n = a + 2, . . . ) Suponga que 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. ´ Matematica– ´ Induccion p. 4/31

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:

´ Matematica– ´ Induccion p. 5/31

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.

´ Matematica– ´ Induccion p. 5/31

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 . . .

´ Matematica– ´ Induccion p. 5/31

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 . . . suponiendo

que P (k) es verdadera (Hipótesis

inductiva)

´ Matematica– ´ Induccion p. 5/31

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 . . . suponiendo

que P (k) es verdadera (Hipótesis

inductiva) entonces muestre

que P (k + 1) también es verdadera.

´ Matematica– ´ Induccion p. 5/31

Inducción Matemática: Ejemplo 1

Suponiendo como válidas las reglas de derivación d x=1 dx

y que d d d (f (x) · g(x)) = g(x) · f (x) + f (x) · g(x) dx dx dx

´ Matematica– ´ Induccion p. 6/31

Inducción Matemática: Ejemplo 1

Suponiendo como válidas las reglas de derivación d x=1 dx

y que d d d (f (x) · g(x)) = g(x) · f (x) + f (x) · g(x) dx dx dx

Demuestre que para todo entero n ≥ 1 d n x = n xn−1 dx

´ Matematica– ´ Induccion p. 6/31

´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva:

´ Matematica– ´ Induccion p. 7/31

´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 1.

´ Matematica– ´ Induccion p. 7/31

´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 1. La fórmula que debemos demostrar para n = 1 queda: d 1 x = 1 x1−1 dx

´ Matematica– ´ Induccion p. 7/31

´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 1. La fórmula que debemos demostrar para n = 1 queda: d 1 x = 1 x1−1 dx

es decir, d x=1 dx pero esto es uno de los datos que tenemos en el problema. Por tanto, la afirmación es cierta para n = 1. ´ Matematica– ´ Induccion p. 7/31

Paso inductivo:

Supongamos que para un entero k ≥ 1 cualquiera se cumple: d k x = k xk−1 dx

´ Matematica– ´ Induccion p. 8/31

Paso inductivo:

Supongamos que para un entero k ≥ 1 cualquiera se cumple: d k x = k xk−1 dx Mostremos que entonces se cumple: d k+1 x = (k + 1) xk+1−1 = (k + 1) xk dx

(La igualdad anterior se debe probar)

´ Matematica– ´ Induccion p. 8/31

Paso inductivo:

Supongamos que para un entero k ≥ 1 cualquiera se cumple: d k x = k xk−1 dx Mostremos que entonces se cumple: d k+1 x = (k + 1) xk+1−1 = (k + 1) xk dx

(La igualdad anterior se debe probar) Trabajemos con el lado izquierdo de la igualdad que queremos demostrar y hagamos un truco matemático:

´ Matematica– ´ Induccion p. 8/31

Paso inductivo:

Supongamos que para un entero k ≥ 1 cualquiera se cumple: d k x = k xk−1 dx Mostremos que entonces se cumple: d k+1 x = (k + 1) xk+1−1 = (k + 1) xk dx

(La igualdad anterior se debe probar) Trabajemos con el lado izquierdo de la igualdad que queremos demostrar y hagamos un truco matemático: d k+1 d ³ k ´ x = x ·x dx dx

´ Matematica– ´ Induccion p. 8/31

Si tomamos como f (x) = xk y como g(x) = x y utilizamos como probada al fórmula dada al inicio del problema tenemos´:

´ Matematica– ´ Induccion p. 9/31

Si tomamos como f (x) = xk y como g(x) = x y utilizamos como probada al fórmula dada al inicio del problema tenemos´: d k d ³ k ´ d k+1 k d x = x ·x =x x +x x dx dx dx dx

´ Matematica– ´ Induccion p. 9/31

Si tomamos como f (x) = xk y como g(x) = x y utilizamos como probada al fórmula dada al inicio del problema tenemos´: d k d ³ k ´ d k+1 k d x = x ·x =x x +x x dx dx dx dx

d k Por la hipótesis inductiva dx x = k xk−1 , entonces tenemos que la igualdad anterior queda:

´ Matematica– ´ Induccion p. 9/31

Si tomamos como f (x) = xk y como g(x) = x y utilizamos como probada al fórmula dada al inicio del problema tenemos´: d k d ³ k ´ d k+1 k d x = x ·x =x x +x x dx dx dx dx

d k Por la hipótesis inductiva dx x = k xk−1 , entonces tenemos que la igualdad anterior queda:

d k+1 d k k d x =x x +x x = x·k xk−1 + xk · 1 dx dx dx

´ Matematica– ´ Induccion p. 9/31

Si tomamos como f (x) = xk y como g(x) = x y utilizamos como probada al fórmula dada al inicio del problema tenemos´: d k d ³ k ´ d k+1 k d x = x ·x =x x +x x dx dx dx dx

d k Por la hipótesis inductiva dx x = k xk−1 , entonces tenemos que la igualdad anterior queda:

d k+1 d k k d x =x x +x x = x·k xk−1 + xk · 1 dx dx dx

Si hacemos álgebra en el lado derecho obtenemos:

´ Matematica– ´ Induccion p. 9/31

Si tomamos como f (x) = xk y como g(x) = x y utilizamos como probada al fórmula dada al inicio del problema tenemos´: d k d ³ k ´ d k+1 k d x = x ·x =x x +x x dx dx dx dx

d k Por la hipótesis inductiva dx x = k xk−1 , entonces tenemos que la igualdad anterior queda:

d k+1 d k k d x =x x +x x = x·k xk−1 + xk · 1 dx dx dx

Si hacemos álgebra en el lado derecho obtenemos: d k+1 x = (k + 1) xk dx

´ Matematica– ´ Induccion p. 9/31

Que era la fórmula que debíamos demostrar. Por tanto d k hemos probado que si dx x = k xk−1 es verdadera, d k+1 x = (k + 1) xk es también verdadera. entonces dx

´ Matematica– ´ Induccion p. 10/31

Que era la fórmula que debíamos demostrar. Por tanto d k hemos probado que si dx x = k xk−1 es verdadera, d k+1 x = (k + 1) xk es también verdadera. entonces dx Es decir, hemos probado el paso inductivo.

´ Matematica– ´ Induccion p. 10/31

Que era la fórmula que debíamos demostrar. Por tanto d k hemos probado que si dx x = k xk−1 es verdadera, d k+1 x = (k + 1) xk es también verdadera. entonces dx Es decir, hemos probado el paso inductivo. Por haber probado la base inductiva y el paso inductivo, el principio de inducción matemática dice que la afirmación es cierta:

´ Matematica– ´ Induccion p. 10/31

Que era la fórmula que debíamos demostrar. Por tanto d k hemos probado que si dx x = k xk−1 es verdadera, d k+1 x = (k + 1) xk es también verdadera. entonces dx Es decir, hemos probado el paso inductivo. Por haber probado la base inductiva y el paso inductivo, el principio de inducción matemática dice que la afirmación es cierta: d n Para todo entero n ≥ 1, x = n xn−1 . dx

´ Matematica– ´ Induccion p. 10/31

Inducción Matemática: Ejemplo 2

Demuestre que para enteros n ≥ 3: 2 n + 1 ≤ 2n

´ Matematica– ´ Induccion p. 11/31

Inducción Matemática: Ejemplo 2

Demuestre que para enteros n ≥ 3: 2 n + 1 ≤ 2n ´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva:

´ Matematica– ´ Induccion p. 11/31

Inducción Matemática: Ejemplo 2

Demuestre que para enteros n ≥ 3: 2 n + 1 ≤ 2n ´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 3.

´ Matematica– ´ Induccion p. 11/31

Inducción Matemática: Ejemplo 2

Demuestre que para enteros n ≥ 3: 2 n + 1 ≤ 2n ´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 3. La desigualdad que debemos demostrar para n = 3 queda: 2 · 3 + 1 ≤ 23

´ Matematica– ´ Induccion p. 11/31

Inducción Matemática: Ejemplo 2

Demuestre que para enteros n ≥ 3: 2 n + 1 ≤ 2n ´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 3. La desigualdad que debemos demostrar para n = 3 queda: 2 · 3 + 1 ≤ 23

es decir, 7 ≤ 8, pero esto es verdadero. ´ Matematica– ´ Induccion p. 11/31

Inducción Matemática: Ejemplo 2

Demuestre que para enteros n ≥ 3: 2 n + 1 ≤ 2n ´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 3. La desigualdad que 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. ´ Matematica– ´ Induccion p. 11/31

Paso inductivo:

Supongamos que para un entero k ≥ 3 cualquiera se cumple: 2 k + 1 ≤ 2k

2 (k + 1) + 1 ≤ 2k+1

(La desigualdad anterior se debe probar)

´ Matematica– ´ Induccion p. 12/31

Paso inductivo:

Supongamos que para un entero k ≥ 3 cualquiera se cumple: 2 k + 1 ≤ 2k Mostremos que entonces se cumple: 2 (k + 1) + 1 ≤ 2k+1

(La desigualdad anterior se debe probar)

´ Matematica– ´ Induccion p. 12/31

Paso inductivo:

Supongamos que para un entero k ≥ 3 cualquiera se cumple: 2 k + 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 la desigualdad que queremos demostrar:

´ Matematica– ´ Induccion p. 12/31

Paso inductivo:

Supongamos que para un entero k ≥ 3 cualquiera se cumple: 2 k + 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 la desigualdad que queremos demostrar: LHS = 2 (k + 1) + 1 = 2 k + 1 + 2

´ Matematica– ´ Induccion p. 12/31

Por la hipótesis inductiva 2 k + 1 ≤ 2k y como para k ≥ 3, 2 ≤ 2k , lo anterior queda: LHS = 2 (k + 1) + 1 = 2 k + 1 + 2

´ Matematica– ´ Induccion p. 13/31

Por la hipótesis inductiva 2 k + 1 ≤ 2k y como para k ≥ 3, 2 ≤ 2k , lo anterior queda: LHS = 2 (k + 1) + 1 = 2 k + 1 + 2 ≤ 2k + 2

´ Matematica– ´ Induccion p. 13/31

Por la hipótesis inductiva 2 k + 1 ≤ 2k y como para k ≥ 3, 2 ≤ 2k , lo anterior queda: LHS = 2 (k + 1) + 1 = 2 k + 1 + 2 ≤ 2k + 2 ≤ 2k + 2k

´ Matematica– ´ Induccion p. 13/31

Por la hipótesis inductiva 2 k + 1 ≤ 2k y como para k ≥ 3, 2 ≤ 2k , lo anterior queda: LHS = 2 (k + 1) + 1 = 2 k + 1 + 2 ≤ 2k + 2 ≤ 2k + 2k

Por tanto, hemos probado que 2 (k + 1) + 1 ≤ 2k + 2k

´ Matematica– ´ Induccion p. 13/31

Por la hipótesis inductiva 2 k + 1 ≤ 2k y como para k ≥ 3, 2 ≤ 2k , lo anterior queda: LHS = 2 (k + 1) + 1 = 2 k + 1 + 2 ≤ 2k + 2 ≤ 2k + 2k

Por tanto, hemos probado que 2 (k + 1) + 1 ≤ 2k + 2k = 2 · 2k

´ Matematica– ´ Induccion p. 13/31

Por la hipótesis inductiva 2 k + 1 ≤ 2k y como para k ≥ 3, 2 ≤ 2k , lo anterior queda: LHS = 2 (k + 1) + 1 = 2 k + 1 + 2 ≤ 2k + 2 ≤ 2k + 2k

Por tanto, hemos probado que 2 (k + 1) + 1 ≤ 2k + 2k = 2 · 2k = 2k+1

´ Matematica– ´ Induccion p. 13/31

Por la hipótesis inductiva 2 k + 1 ≤ 2k y como para k ≥ 3, 2 ≤ 2k , lo anterior queda: LHS = 2 (k + 1) + 1 = 2 k + 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.

´ Matematica– ´ Induccion p. 13/31

Por la hipótesis inductiva 2 k + 1 ≤ 2k y como para k ≥ 3, 2 ≤ 2k , lo anterior queda: LHS = 2 (k + 1) + 1 = 2 k + 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. Por tanto, hemos probado el paso inductivo.

´ Matematica– ´ Induccion p. 13/31

Por la hipótesis inductiva 2 k + 1 ≤ 2k y como para k ≥ 3, 2 ≤ 2k , lo anterior queda: LHS = 2 (k + 1) + 1 = 2 k + 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. Por tanto, hemos probado el paso inductivo. Por el principio de inducción matemática la afirmación es verdadera: Para cualquier entero n ≥ 3, 2 n + 2 ≤ 2n

´ Matematica– ´ Induccion p. 13/31

Note que en la demostración anterior hemos hecho uso de lo siguiente: Si A ≤ B , entonces A + C ≤ B + C . Si A ≤ B y B ≤ C , entonces A ≤ C .

´ Matematica– ´ Induccion p. 14/31

Inducción Matemática: Ejemplo 3

Demuestre que para enteros n ≥ 4: n2 ≤ 2n

´ Matematica– ´ Induccion p. 15/31

Inducción Matemática: Ejemplo 3

Demuestre que para enteros n ≥ 4: n2 ≤ 2n ´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva:

´ Matematica– ´ Induccion p. 15/31

Inducción Matemática: Ejemplo 3

Demuestre que para enteros n ≥ 4: n2 ≤ 2n ´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 4.

´ Matematica– ´ Induccion p. 15/31

Inducción Matemática: Ejemplo 3

Demuestre que para enteros n ≥ 4: n2 ≤ 2n ´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 4. La desigualdad que debemos demostrar para n = 4 queda: 42 ≤ 24

´ Matematica– ´ Induccion p. 15/31

Inducción Matemática: Ejemplo 3

Demuestre que para enteros n ≥ 4: n2 ≤ 2n ´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 4. La desigualdad que debemos demostrar para n = 4 queda: 42 ≤ 24

es decir, 16 ≤ 16, pero esto es verdadero. ´ Matematica– ´ Induccion p. 15/31

Inducción Matemática: Ejemplo 3

Demuestre que para enteros n ≥ 4: n2 ≤ 2n ´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 4. La desigualdad que debemos demostrar para n = 4 queda: 42 ≤ 24

es decir, 16 ≤ 16, pero esto es verdadero. Por tanto, la afirmación es cierta para n = 4. ´ Matematica– ´ Induccion p. 15/31

Paso inductivo:

Supongamos que para un entero k ≥ 4 cualquiera se cumple: k 2 ≤ 2k

(k + 1)2 ≤ 2k+1

(La desigualdad anterior se debe probar)

´ Matematica– ´ Induccion p. 16/31

Paso inductivo:

Supongamos que para un entero k ≥ 4 cualquiera se cumple: k 2 ≤ 2k Mostremos que entonces se cumple: (k + 1)2 ≤ 2k+1

(La desigualdad anterior se debe probar)

´ Matematica– ´ Induccion p. 16/31

Paso inductivo:

Supongamos que para un entero k ≥ 4 cualquiera se cumple: k 2 ≤ 2k Mostremos que entonces se cumple: LHS = (k + 1)2 ≤ 2k+1

(La desigualdad anterior se debe probar) Trabajemos con el lado izquierdo de la desigualdad que queremos demostrar:

´ Matematica– ´ Induccion p. 16/31

Paso inductivo:

Supongamos que para un entero k ≥ 4 cualquiera se cumple: k 2 ≤ 2k Mostremos que entonces se cumple: LHS = (k + 1)2 ≤ 2k+1

(La desigualdad anterior se debe probar) Trabajemos con el lado izquierdo de la desigualdad que queremos demostrar: LHS = (k + 1)2 = k 2 + 2 k + 1

´ Matematica– ´ Induccion p. 16/31

Por la hipótesis inductiva k 2 ≤ 2k y como para k ≥ 4 ≥ 3, 2 k + 1 ≤ 2k , lo anterior queda: LHS = (k + 1)2 = k 2 + 2 k + 1

´ Matematica– ´ Induccion p. 17/31

Por la hipótesis inductiva k 2 ≤ 2k y como para k ≥ 4 ≥ 3, 2 k + 1 ≤ 2k , lo anterior queda: LHS = (k + 1)2 = k 2 + 2 k + 1 ≤ 2k + 2 k + 1

´ Matematica– ´ Induccion p. 17/31

Por la hipótesis inductiva k 2 ≤ 2k y como para k ≥ 4 ≥ 3, 2 k + 1 ≤ 2k , lo anterior queda: LHS = (k + 1)2 = k 2 + 2 k + 1 ≤ 2k + 2 k + 1 ≤ 2k + 2k

´ Matematica– ´ Induccion p. 17/31

Por la hipótesis inductiva k 2 ≤ 2k y como para k ≥ 4 ≥ 3, 2 k + 1 ≤ 2k , lo anterior queda: LHS = (k + 1)2 = k 2 + 2 k + 1 ≤ 2k + 2 k + 1 ≤ 2k + 2k

Por tanto, hemos probado que (k + 1)2 ≤ 2k + 2k

´ Matematica– ´ Induccion p. 17/31

Por la hipótesis inductiva k 2 ≤ 2k y como para k ≥ 4 ≥ 3, 2 k + 1 ≤ 2k , lo anterior queda: LHS = (k + 1)2 = k 2 + 2 k + 1 ≤ 2k + 2 k + 1 ≤ 2k + 2k

Por tanto, hemos probado que (k + 1)2 ≤ 2k + 2k = 2 · 2k

´ Matematica– ´ Induccion p. 17/31

Por la hipótesis inductiva k 2 ≤ 2k y como para k ≥ 4 ≥ 3, 2 k + 1 ≤ 2k , lo anterior queda: LHS = (k + 1)2 = k 2 + 2 k + 1 ≤ 2k + 2 k + 1 ≤ 2k + 2k

Por tanto, hemos probado que (k + 1)2 ≤ 2k + 2k = 2 · 2k = 2k+1

´ Matematica– ´ Induccion p. 17/31

Por la hipótesis inductiva k 2 ≤ 2k y como para k ≥ 4 ≥ 3, 2 k + 1 ≤ 2k , lo anterior queda: LHS = (k + 1)2 = k 2 + 2 k + 1 ≤ 2k + 2 k + 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.

´ Matematica– ´ Induccion p. 17/31

Por la hipótesis inductiva k 2 ≤ 2k y como para k ≥ 4 ≥ 3, 2 k + 1 ≤ 2k , lo anterior queda: LHS = (k + 1)2 = k 2 + 2 k + 1 ≤ 2k + 2 k + 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. Por tanto, hemos probado el paso inductivo.

´ Matematica– ´ Induccion p. 17/31

Por la hipótesis inductiva k 2 ≤ 2k y como para k ≥ 4 ≥ 3, 2 k + 1 ≤ 2k , lo anterior queda: LHS = (k + 1)2 = k 2 + 2 k + 1 ≤ 2k + 2 k + 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. Por tanto, hemos probado el paso inductivo. Por el principio de inducción matemática la afirmación es verdadera: Para cualquier entero n ≥ 4, n2 ≤ 2n

´ Matematica– ´ Induccion p. 17/31

Inducción Matemática: Ejemplo 4

Demuestre que para enteros n ≥ 1: 1 + 2 + ··· + n =

k X i=1

n(n + 1) i= 2

´ Matematica– ´ Induccion p. 18/31

Inducción Matemática: Ejemplo 4

Demuestre que para enteros n ≥ 1: 1 + 2 + ··· + n =

k X i=1

n(n + 1) i= 2

´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva:

´ Matematica– ´ Induccion p. 18/31

Inducción Matemática: Ejemplo 4

Demuestre que para enteros n ≥ 1: 1 + 2 + ··· + n =

k X i=1

n(n + 1) i= 2

´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 1.

´ Matematica– ´ Induccion p. 18/31

Inducción Matemática: Ejemplo 4

Demuestre que para enteros n ≥ 1: 1 + 2 + ··· + n =

k X i=1

n(n + 1) i= 2

´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 1. La igualdad que debemos demostrar para n = 1 queda: 1 X i=1

1 · (1 + 1) i=1= =1 2 ´ Matematica– ´ Induccion p. 18/31

Paso inductivo:

Supongamos que para un entero k ≥ 1 cualquiera se cumple: k X k(k + 1) i= 2 i=1

k+1 X i=1

(k + 1)(k + 1 + 1) (k + 1)(k + 2) i= = 2 2

(La igualdad anterior se debe probar)

´ Matematica– ´ Induccion p. 19/31

Paso inductivo:

Supongamos que para un entero k ≥ 1 cualquiera se cumple: k X k(k + 1) i= 2 i=1

Mostremos que entonces se cumple: k+1 X i=1

(k + 1)(k + 1 + 1) (k + 1)(k + 2) i= = 2 2

(La igualdad anterior se debe probar)

´ Matematica– ´ Induccion p. 19/31

Paso inductivo:

Supongamos que para un entero k ≥ 1 cualquiera se cumple: k X k(k + 1) i= 2 i=1

Mostremos que entonces se cumple: LHS =

k+1 X i=1

(k + 1)(k + 1 + 1) (k + 1)(k + 2) i= = 2 2

(La igualdad anterior se debe probar) Ã k ! k+1 X X i +k+1 i= LHS = i=1

i=1

´ Matematica– ´ Induccion p. 19/31

Por la hipótesis inductiva LHS =

k+1 X i=1

Pk

i=1 i

=

k(k+1) 2

lo anterior queda:

à k ! X i= i +k+1 i=1

´ Matematica– ´ Induccion p. 20/31

Por la hipótesis inductiva LHS =

k+1 X i=1

Pk

i=1 i

=

k(k+1) 2

lo anterior queda:

à k ! X k(k + 1) i= i +k+1= +k+1 2 i=1

´ Matematica– ´ Induccion p. 20/31

Por la hipótesis inductiva LHS =

k+1 X i=1

Pk

i=1 i

=

k(k+1) 2

lo anterior queda:

à k ! X k(k + 1) i= i +k+1= +k+1 2 i=1

Haciendo álgebra tenemos: k(k + 1) +k+1 2

´ Matematica– ´ Induccion p. 20/31

Por la hipótesis inductiva LHS =

k+1 X i=1

Pk

i=1 i

=

k(k+1) 2

lo anterior queda:

à k ! X k(k + 1) i= i +k+1= +k+1 2 i=1

Haciendo álgebra tenemos: k(k + 1) k(k + 1) + 2(k + 1) +k+1= 2 2

´ Matematica– ´ Induccion p. 20/31

Por la hipótesis inductiva LHS =

k+1 X i=1

Pk

i=1 i

=

k(k+1) 2

lo anterior queda:

à k ! X k(k + 1) i= i +k+1= +k+1 2 i=1

Haciendo álgebra tenemos: k(k + 1) k(k + 1) + 2(k + 1) (k + 1)(k + 2) +k+1= = 2 2 2

´ Matematica– ´ Induccion p. 20/31

Por tanto, hemos probado que k+1 X i=1

(k + 1)(k + 2) i= 2

´ Matematica– ´ Induccion p. 21/31

Por tanto, hemos probado que k+1 X i=1

(k + 1)(k + 2) i= 2

Esto es justo la afirmación para n = k + 1.

´ Matematica– ´ Induccion p. 21/31

Por tanto, hemos probado que k+1 X i=1

(k + 1)(k + 2) i= 2

Esto es justo la afirmación para n = k + 1. Por tanto, hemos probado el paso inductivo.

´ Matematica– ´ Induccion p. 21/31

Por tanto, hemos probado que k+1 X i=1

(k + 1)(k + 2) i= 2

Esto es justo la afirmación para n = k + 1. Por tanto, hemos probado el paso inductivo. Por el principio de inducción matemática la afirmación es verdadera: Para cualquier entero n ≥ 1,

n X i=1

n(n + 1) i= 2

´ Matematica– ´ Induccion p. 21/31

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 = 2 an + 1 para n ≥ 1.

´ Matematica– ´ Induccion p. 22/31

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 = 2 an + 1 para n ≥ 1. Pruebe que la fórmula para los números an para n ≥ 1 es: an = 2n − 1

´ Matematica– ´ Induccion p. 22/31

´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva:

´ Matematica– ´ Induccion p. 23/31

´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 1.

´ Matematica– ´ Induccion p. 23/31

´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 1. La igualdad que debemos demostrar para n = 1 queda: a1 = 21 − 1 = 1

´ Matematica– ´ Induccion p. 23/31

´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 1. La igualdad que debemos demostrar para n = 1 queda: a1 = 21 − 1 = 1

pero esto es verdadero por la regla 1.

´ Matematica– ´ Induccion p. 23/31

´ Demostracion

De acuerdo al principio de inducción matemática debemos demostrar: Base inductiva: Que la afirmación es veradera para el primero de esos enteros. En este caso n = 1. La igualdad que debemos 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.

´ Matematica– ´ Induccion p. 23/31

Paso inductivo:

Supongamos que para un entero k ≥ 1 cualquiera se cumple: ak = 2k − 1

´ Matematica– ´ Induccion p. 24/31

Paso inductivo:

Supongamos que para un entero k ≥ 1 cualquiera se cumple: ak = 2k − 1 Mostremos que entonces se cumple: ak+1 = 2k+1 − 1

(La igualdad anterior se debe probar)

´ Matematica– ´ Induccion p. 24/31

Paso inductivo:

Supongamos que para un entero k ≥ 1 cualquiera se cumple: ak = 2k − 1 Mostremos que entonces se cumple: ak+1 = 2k+1 − 1

(La igualdad anterior se debe probar) Trabajemos con el lado izquierdo de la igualdad que queremos demostrar: por la regla 2: ak+1 = 2 ak + 1

´ Matematica– ´ Induccion p. 24/31

Por la hipótesis inductiva ak = 2k − 1 lo anterior queda: ak+1 = 2 ak + 1

´ Matematica– ´ Induccion p. 25/31

Por la hipótesis inductiva ak = 2k − 1 lo anterior queda: ak+1 = 2 ak + 1 = 2(2k − 1) + 1

´ Matematica– ´ Induccion p. 25/31

Por la hipótesis inductiva ak = 2k − 1 lo anterior queda: ak+1 = 2 ak + 1 = 2(2k − 1) + 1 = 2k+1 − 1

´ Matematica– ´ Induccion p. 25/31

Por la hipótesis inductiva ak = 2k − 1 lo anterior queda: ak+1 = 2 ak + 1 = 2(2k − 1) + 1 = 2k+1 − 1

Por tanto, hemos probado que ak+1 = 2k+1 − 1

´ Matematica– ´ Induccion p. 25/31

Por la hipótesis inductiva ak = 2k − 1 lo anterior queda: ak+1 = 2 ak + 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.

´ Matematica– ´ Induccion p. 25/31

Por la hipótesis inductiva ak = 2k − 1 lo anterior queda: ak+1 = 2 ak + 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. Por tanto, hemos probado el paso inductivo.

´ Matematica– ´ Induccion p. 25/31

Por la hipótesis inductiva ak = 2k − 1 lo anterior queda: ak+1 = 2 ak + 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. Por tanto, hemos probado el paso inductivo. Por el principio de inducción matemática la afirmación es verdadera: Para cualquier entero n ≥ 1, an = 2n − 1

´ Matematica– ´ Induccion p. 25/31

Inducción Matemática: Ejemplo 6

Considere el programa: SD(A,n,x)

´ Matematica– ´ Induccion p. 26/31

Inducción Matemática: Ejemplo 6

Considere el programa: SD(A,n,x) variable A array of float variable n integer variable x float

´ Matematica– ´ Induccion p. 26/31

Inducción Matemática: Ejemplo 6

Considere el programa: SD(A,n,x) variable A array of float variable n integer variable x float if (n = 1) then [a]

return(A[1])

´ Matematica– ´ Induccion p. 26/31

Inducción Matemática: Ejemplo 6

Considere el programa: SD(A,n,x) variable A array of float variable n integer variable x float if (n = 1) then [a]

return(A[1])

else [b]

return(A[n] + x*SD(A,n-1,x))

´ Matematica– ´ Induccion p. 26/31

Inducción Matemática: Ejemplo 6

Considere el programa: SD(A,n,x) variable A array of float variable n integer variable x float if (n = 1) then [a]

return(A[1])

else [b]

return(A[n] + x*SD(A,n-1,x))

end if end proc

´ Matematica– ´ Induccion p. 26/31

Inducción Matemática: Ejemplo 6

Considere el programa:

Afirmación para n ≥ 1:

SD(A,n,x) variable A array of float variable n integer

SD(A, n, x)

= =

Pn

i=1

A[i]xn−i

A[n] + A[n − 1] x1 + · · · + A[1] xn−1

variable x float if (n = 1) then [a]

return(A[1])

else [b]

return(A[n] + x*SD(A,n-1,x))

end if end proc

´ Matematica– ´ Induccion p. 26/31

Inducción Matemática: Ejemplo 6

Considere el programa:

Afirmación para n ≥ 1:

SD(A,n,x) variable A array of float variable n integer variable x float if (n = 1) then [a]

return(A[1])

SD(A, n, x)

= =

Pn

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.

else [b]

return(A[n] + x*SD(A,n-1,x))

end if end proc

´ Matematica– ´ Induccion p. 26/31

´ Demostracion Base inductiva:

´ Matematica– ´ Induccion p. 27/31

´ Demostracion Base inductiva:

Debemos demostrar que para n = 1 el programa regresa : 1 X

A[i] x1−i = A[1] x1−1 = A[1].

i=1

´ Matematica– ´ Induccion p. 27/31

´ Demostracion Base inductiva:

Debemos demostrar que para n = 1 el programa regresa : 1 X

A[i] x1−i = A[1] x1−1 = A[1].

i=1

Pero esto es verdadero, pues el programa para n = 1 sale por la línea [a] entregando esto.

´ Matematica– ´ Induccion p. 27/31

´ Demostracion Base inductiva:

Debemos demostrar que para n = 1 el programa regresa : 1 X

A[i] x1−i = A[1] x1−1 = A[1].

i=1

Pero esto es verdadero, pues el programa para n = 1 sale por la línea [a] entregando esto. Además, como no realiza ninguna operación de punto flotante se coincide con la fórmula para el número de FLOPs invertidos: 2 (1 − 1) = 0.

´ Matematica– ´ Induccion p. 27/31

´ Demostracion Base inductiva:

Debemos demostrar que para n = 1 el programa regresa : 1 X

A[i] x1−i = A[1] x1−1 = A[1].

i=1

Pero esto es verdadero, pues el programa para n = 1 sale por la línea [a] entregando esto. Además, como no realiza ninguna operación de punto flotante se coincide con la fórmula para el número de FLOPs invertidos: 2 (1 − 1) = 0. Por tanto, la afirmación es cierta para n = 1.

´ Matematica– ´ Induccion p. 27/31

Paso inductivo:

Supongamos que para un entero k ≥ 1 cualquiera se cumple: k X SD(A, k, x) = A[i]xk−i i=1

Y que lo hace con 2(k − 1) FLOPs.

´ Matematica– ´ Induccion p. 28/31

Paso inductivo:

Supongamos que para un entero k ≥ 1 cualquiera se cumple: k X SD(A, k, x) = A[i]xk−i i=1

Y que lo hace con 2(k − 1) FLOPs. Mostremos que entonces se cumple: SD(A, k + 1, x) =

k+1 X

A[i]xk+1−i

i=1

´ Matematica– ´ Induccion p. 28/31

Paso inductivo:

Supongamos que para un entero k ≥ 1 cualquiera se cumple: k X SD(A, k, x) = A[i]xk−i i=1

Y que lo hace con 2(k − 1) FLOPs. Mostremos que entonces se cumple: SD(A, k + 1, x) =

k+1 X

A[i]xk+1−i

i=1

y que lo hace en 2(k + 1 − 1) = 2 k FLOPs. ´ Matematica– ´ Induccion p. 28/31

Revisemos la ejecución del programa para n = k + 1:

´ Matematica– ´ Induccion p. 29/31

Revisemos la ejecución del programa para n = k + 1: Como k ≥ 1 entonces k + 1 6= 1.

´ Matematica– ´ Induccion p. 29/31

Revisemos la ejecución del programa para n = k + 1: Como k ≥ 1 entonces k + 1 6= 1. Por lo tanto, el programa ejecuta la línea [b] entregando:

´ Matematica– ´ Induccion p. 29/31

Revisemos la ejecución del programa para n = k + 1: Como k ≥ 1 entonces k + 1 6= 1. Por lo tanto, el programa ejecuta la línea [b] entregando: SD(A, k + 1, x) = A[n] + x × SD(A, k, x)

´ Matematica– ´ Induccion p. 29/31

Revisemos la ejecución del programa para n = k + 1: Como k ≥ 1 entonces k + 1 6= 1. Por lo tanto, 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 X

A[i]xk−i

i=1

´ Matematica– ´ Induccion p. 29/31

Revisemos la ejecución del programa para n = k + 1: Como k ≥ 1 entonces k + 1 6= 1. Por lo tanto, 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 X

A[i]xk−i

i=1

Por propiedades matemáticas lo anterior queda: SD(A, k + 1, x) = A[n] +

k X i=1

A[i]xk+1−i =

k+1 X

A[i]xk+1−i

i=1

´ Matematica– ´ Induccion p. 29/31

Además, haciendo en conteo de las operaciones realizadas

´ Matematica– ´ Induccion p. 30/31

Además, haciendo en conteo de las operaciones realizadas la llamada recursiva requerirá 2(k − 1) FLOPs, y

´ Matematica– ´ Induccion p. 30/31

Además, haciendo en conteo de las operaciones realizadas 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.

´ Matematica– ´ Induccion p. 30/31

Además, haciendo en conteo de las operaciones realizadas 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 operaciones involucradas serán 2(k − 1) + 2 = 2 k

´ Matematica– ´ Induccion p. 30/31

Además, haciendo en conteo de las operaciones realizadas 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 operaciones involucradas serán 2(k − 1) + 2 = 2 k

Esto es exactamente lo que se quería demostrar.

´ Matematica– ´ Induccion p. 30/31

Por tanto, hemos probado que bajo la hipótesis inductiva,

´ Matematica– ´ Induccion p. 31/31

Por tanto, hemos probado que bajo la hipótesis inductiva, validez de lo afirmado para n = k ,

´ Matematica– ´ Induccion p. 31/31

Por tanto, hemos probado que bajo la hipótesis inductiva, validez de lo afirmado para n = k , el programa ejecutado para n = k + 1 entrega SD(A, k + 1, x) =

k+1 X

A[i]xk+1−i

i=1

´ Matematica– ´ Induccion p. 31/31

Por tanto, hemos probado que bajo la hipótesis inductiva, validez de lo afirmado para n = k , el programa ejecutado para n = k + 1 entrega SD(A, k + 1, x) =

k+1 X

A[i]xk+1−i

i=1

y lo hace en 2(k + 1 − 1) FLOPs.

´ Matematica– ´ Induccion p. 31/31

Por tanto, hemos probado que bajo la hipótesis inductiva, validez de lo afirmado para n = k , el programa ejecutado para n = k + 1 entrega SD(A, k + 1, x) =

k+1 X

A[i]xk+1−i

i=1

y lo hace en 2(k + 1 − 1) FLOPs. Lo que es exactamente la afirmación para n = k + 1.

´ Matematica– ´ Induccion p. 31/31

Por tanto, hemos probado que bajo la hipótesis inductiva, validez de lo afirmado para n = k , el programa ejecutado para n = k + 1 entrega SD(A, k + 1, x) =

k+1 X

A[i]xk+1−i

i=1

y lo hace en 2(k + 1 − 1) FLOPs. Lo que es exactamente la afirmación para n = k + 1. Por tanto, hemos probado el paso inductivo.

´ Matematica– ´ Induccion p. 31/31

Por tanto, hemos probado que bajo la hipótesis inductiva, validez de lo afirmado para n = k , el programa ejecutado para n = k + 1 entrega SD(A, k + 1, x) =

k+1 X

A[i]xk+1−i

i=1

y lo hace en 2(k + 1 − 1) FLOPs. Lo que es exactamente la afirmación para n = k + 1. Por tanto, hemos probado el paso inductivo. Por el principio de inducción matemática la afirmación es verdadera para enteros n ≥ 1.

´ Matematica– ´ Induccion p. 31/31