Ejercicios resueltos induccion (2014)

Ejercicio Español
Universidad Universidad Politécnica de Cataluña (UPC)
Grado Ingeniería Civil - 1º curso
Asignatura Fundamentos Matematicos
Año del apunte 2014
Páginas 9
Fecha de subida 03/06/2014
Descargas 1

Descripción

Ejercicios de la coleccion resueltos.

Vista previa del texto

EJERCICIOS RESUELTOS DE INDUCCIÓN MATEMÁTICA Comprobamos que la igualdad se cumple para 𝑛 = 1 1= 1(1 + 1) 2 = =1 2 2 Planteamos nuestra hipótesis de inducción, es decir, suponemos que se cumple para 𝑛 = 𝑘 1 + 2 + ⋯+ 𝑘 = 𝑘(𝑘 + 1) 𝐻𝐼 2 Que se cumple para 𝑛 = 𝑘 ⇒ se cumple para n= 𝑘 + 1. Luego hemos de comprobar que se cumple para 𝑛 = 𝑘 + 1. Para ello planteamos la igualdad nuevamente y desarrollamos al menos uno de los dos lados de la igualdad.
1 + 2 + ⋯ + 𝑘 + (𝑘 + 1) = Desarrollamos el lado derecho: (𝑘 + 1)[(𝑘 + 1) + 1] 2 (𝑘 + 1)[(𝑘 + 1) + 1] (𝑘 + 1)(𝑘 + 2) 𝑘 2 + 2𝑘 + 𝑘 + 2 𝑘 2 + 𝑘 2𝑘 + 2 𝑘(𝑘 + 1) 2𝑘 + 2 = = = + = + = 2 2 2 2 2 2 2 = 1 + 2 + ⋯+ 𝑘 + Verificamos igualdad con 𝑛 = 1 12 = 2𝑘 + 2 = 1 + 2 + ⋯ + 𝑘 + (𝑘 + 1) ∎ 2 1(1 + 1)(2 + 1) 1 · 2 · 3 6 = = =1 6 6 6 Suponemos que se cumple para 𝑛 = 𝑘 − 1 (hipótesis de inducción): 12 + 22 + ⋯ + (𝑘 − 1)2 = (𝑘 − 1)(𝑘 − 1 + 1)(2(𝑘 − 1) + 1) 𝑘(𝑘 − 1)(2𝑘 − 1) 2𝑘 3 − 3𝑘 2 + 𝑘 = = 𝐻𝐼 6 6 6 Lo cual implicará que se cumple para 𝑛 = 𝑘 (resultado al que queremos llegar): 12 + 22 + ⋯ + (𝑘 − 1)2 + 𝑘 2 = Lo comprobamos desarrollando el lado derecho: 𝑘(𝑘 + 1)(2𝑘 + 1) 6 𝑘(𝑘 + 1)(2𝑘 + 1) 2𝑘 3 + 3𝑘 2 + 𝑘 2𝑘 3 + 3𝑘 2 + 𝑘 − 6𝑘 2 2𝑘 3 − 3𝑘 2 + 𝑘 = − 𝑘2 + 𝑘2 = + 𝑘2 = + 𝑘2 = 6 6 6 6 12 + 22 + ⋯ + (𝑘 − 1)2 + 𝑘 2 ∎ Verificamos 𝑛 = 1 Verificamos 𝑛 = 2 1 1 1 = = 3 2+1 3 1 1 1 1 6 2 2 2 + = + = = ; = 1 · 3 3 · 5 3 15 15 5 2·2+1 5 Suponemos que se cumple para 𝑛 = 𝑘 (hipótesis de inducción): 1 𝑘 1 + ⋯+ = 𝐻𝐼 (2𝑘 − 1)(2𝑘 + 1) 2𝑘 + 1 1·3 Implicará que se cumple para 𝑛 = 𝑘 + 1 . Es decir, se cumple: 1 1 𝑘+1 1 + ⋯+ + = (2𝑘 − 1)(2𝑘 + 1) (2(𝑘 + 1) − 1) · (2(𝑘 + 1) + 1) 2(𝑘 + 1) + 1 1·3 Para simplificar, reexpresamos la igualdad: 1 1 𝑘+1 1 +⋯+ + = (2𝑘 − 1)(2𝑘 + 1) (2𝑘 + 1)(2𝑘 + 3) 2𝑘 + 3 1·3 Desarrollamos lado izquierdo: 1 1 1 𝑘 1 𝑘(2𝑘 + 3) + 1 + ⋯+ + = + = = (2𝑘 − 1)(2𝑘 + 1) (2𝑘 + 1)(2𝑘 + 3) 2𝑘 + 1 (2𝑘 + 1)(2𝑘 + 3) (2𝑘 + 1)(2𝑘 + 3) 1·3 𝑘(2𝑘 + 3) + 1 2𝑘 2 + 3𝑘 + 1 (𝑘 + 1)(2𝑘 + 1) 𝑘+1 = = = ∎ (2𝑘 + 1)(2𝑘 + 3) (2𝑘 + 1)(2𝑘 + 3) (2𝑘 + 1)(2𝑘 + 3) 2𝑘 + 3 Se nos pide que demostremos que ∀𝑛 ∈ ℕ∗ se cumple: Lo demostraremos por inducción: 1 2 𝑛 �𝑛 + � (𝑛 + 1) = 3𝑞 , donde 𝑞 ∈ ℕ Comprobamos que se cumple para 𝑛 = 1 3 1 1 �1 + � (1 + 1) = 1 · · 2 = 3 · 1 2 2 Suponemos cierto que se cumple para 𝑛 = 𝑘 (hipótesis de inducción): 3 𝑘 1 𝑘 �𝑘 + � (𝑘 + 1) = 𝑘 3 + 𝑘 + = 3𝑞 (𝑞 ∈ ℕ∗ ) 𝐻𝐼 2 2 2 Lo cual implicará que se cumple para 𝑛 = 𝑘 + 1 . Es decir, se cumple: 1 2 (𝑘 + 1) �(𝑘 + 1) + � �(𝑘 + 1) + 1� = 3𝑝 (𝑝 ∈ ℕ∗ ) Lo verificamos: 3 𝑘 1 3 (𝑘 + 1) �(𝑘 + 1) + � �(𝑘 + 1) + 1� = (𝑘 + 1) �𝑘 + � (𝑘 + 2) = 𝑘 3 + 𝑘 + + 3𝑘 2 + 6𝑘 + 3 = 2 2 2 2 3𝑞 + 3𝑘 2 + 6𝑘 + 3 = 3𝑞 + 3(𝑘 2 + 2𝑘 + 1) = 3(𝑞 + (𝑘 + 1)2 ) = 3𝑝 ∎ Dado que por hipótesis 𝑞 ∈ ℕ∗ y (𝑘 + 1)2 ∈ ℕ∗ , ya que 𝑘 ∈ ℕ∗ (el cuadrado y la suma de naturales es un número natural) podemos asegurar que 3(𝑝 + (𝑘 + 1)2 ) = 3𝑝, es decir, que es un natural múltiplo de 3.
Comprobamos para 𝑛 = 1 34 + 9 = 81 + 9 = 90 = 10 · 9 Suponemos que se cumple la igualdad para 𝑛 = 𝑘 (hipótesis de inducción) 34𝑘 + 9 = 10𝑞 𝐻𝐼 , donde 𝑞 ∈ ℕ∗ Implica que se cumplirá para 𝑛 = 𝑘 + 1 , es decir: Lo verificamos: 34(𝑘+1) + 9 = 10𝑝 (𝑝 ∈ ℕ∗ ) 34(𝑘+1) + 9 = 34𝑘+4 + 9 = 34𝑘 · 34 + 9 = (10𝑞 − 9) · 34 + 9 = 10𝑞 · 34 − 36 + 32 = 10𝑞 · 34 − 720 = = 10 · (81𝑞 − 72) = 10𝑝 ∎ Ya que 𝑞 ∈ ℕ∗ implica que (81𝑞 − 72) ∈ ℕ∗ Comprobamos para 𝑛 = 1 92 − 8 + 55 = 81 − 8 + 55 = 128 = 64 · 2 Suponemos que se cumple la igualdad para 𝑛 = 𝑘 − 1 (hipótesis de inducción) 9𝑘 − 8(𝑘 − 1) + 55 = 9𝑘 − 8𝑘 + 63 = 64𝑞 𝐻𝐼 , donde 𝑞 ∈ ℕ∗ Implica que se cumplirá para 𝑛 = 𝑘 , es decir: 9𝑘+1 − 8𝑘 + 55 = 64𝑝 (𝑝 ∈ ℕ∗ ) Lo verificamos: 9𝑘+1 − 8𝑘 + 55 = 9𝑘 · 9 − 8𝑘 + 55 = (64𝑞 + 8𝑘 − 63) · 9 − 8𝑘 + 55 = (64 · 9)𝑞 + 64𝑘 − 512 = = (64 · 9)𝑞 + 64𝑘 − (64 · 8) = 64(9𝑞 + 𝑘 − 8) = 64𝑝 ∎ Ya que 𝑞, 𝑘 ∈ ℕ∗ implica que (9𝑞 + 𝑘 − 8) ∈ ℕ∗ Comprobamos para 𝑛 = 1 Comprobamos para 𝑛 = 2 13 + 23 + 33 = 36 = 9 · 4 23 + 33 + 43 = 8 + 27 + 64 = 99 = 9 · 11 Suponemos que se cumple la igualdad para 𝑛 = 𝑘 − 1 (hipótesis de inducción) (𝑘 − 1)3 + 𝑘 3 + (𝑘 + 1)3 = 9𝑞 𝐻𝐼 , donde 𝑞 ∈ ℕ∗ Implica que se cumplirá para 𝑛 = 𝑘 , es decir: Lo verificamos: 𝑘 3 + (𝑘 + 1)3 + (𝑘 + 2)3 = 9𝑝 (𝑝 ∈ ℕ∗ ) 𝑘 3 + (𝑘 + 1)3 + (𝑘 + 2)3 = (𝑘 + 2)3 + 9𝑞 − (𝑘 − 1)3 = 𝑘 3 + 6𝑘 2 + 12𝑘 + 8 + 9𝑞 − (𝑘 3 − 3𝑘 2 + 3𝑘 − 1) = 9𝑘 2 − 9𝑘 + 9 + 9𝑞 = 9 · (𝑘 2 − 𝑘 + 1 + 𝑞) = 9𝑝 ∎ Ya que 𝑞, 𝑘 ∈ ℕ∗ implica que (𝑘 2 − 𝑘 + 1 + 𝑞) ∈ ℕ∗ En primer lugar, probamos con unos cuantos valores iniciales, para hacernos una idea del “comportamiento” de la desigualdad: 𝑛 1 2 3 4 … 2𝑛 2 4 8 16 … 𝑛 < 2𝑛 Verdadero Verdadero Verdadero Verdadero … Parece cumplirse para todo número natural. Demostremos por inducción que se cumple ∀𝑛 ∈ ℕ∗ .
Suponemos cierto que se cumple para 𝑛 = 𝑘 (hipótesis de inducción): 𝑘 < 2𝑘 𝐻𝐼 Lo cual ha de implicar que se cumplirá para 𝑛 = 𝑘 + 1 , es decir: Lo verificamos: 𝑘 + 1 < 2𝑘+1 𝑘 + 1 < 2𝑘 + 1 < 2𝑘 · 2 = 2𝑘+1 ∎ Dado que es evidente que 2𝑘 + 1 < 2𝑘 · 2 (∀𝑘 ∈ ℕ∗ , 𝑘 ≥ 1) Probamos con unos cuantos valores iniciales para hacernos una idea del “comportamiento” de la desigualdad: 𝑛 1 2 3 4 5 6 7 … 𝑛2 1 4 9 16 25 36 49 … 2𝑛 2 4 8 16 32 64 128 … 𝑛 2 < 2𝑛 Verdadero Falso Falso Falso Verdadero Verdadero Verdadero … Parece cumplirse para 𝑛 ≥ 5. Demostremos por inducción que se cumple para 𝑛 ∈ ℕ∗ , 𝑛 ≥ 5.
Suponemos cierto que se cumple para 𝑛 = 𝑘 (hipótesis de inducción): 𝑘 2 < 2𝑘 𝐻𝐼 Lo cual ha de implicar que se cumplirá para 𝑛 = 𝑘 + 1 , es decir: Lo verificamos: (𝑘 + 1)2 < 2𝑘+1 (𝑘 + 1)2 = 𝑘 2 + 2𝑘 + 1 Y dado que 𝑘 2 > 2𝑘 + 1 ⟺ 𝑘 2 − 2𝑘 > 1 ⟺ 𝑘(𝑘 − 2) > 1 se verifica para 𝑘 ≥ 5, 𝑘 ∈ ℕ: 2𝑘+1 = 2𝑘 · 2 > 𝑘 2 · 2 = 𝑘 2 + 𝑘 2 > 𝑘 2 + 2𝑘 + 1 = (𝑘 + 1)2 ∎ Probamos con unos cuantos valores iniciales para hacernos una idea del “comportamiento” de la desigualdad: 𝑛 1 2 3 4 5 6 … 2𝑛 2 4 8 16 32 64 … 𝑛! 1 2 6 24 120 720 2𝑛 < 𝑛! Falso Falso Falso Verdadero Verdadero Verdadero … Parece cumplirse para 𝑛 ≥ 4. Demostremos por inducción que se cumple para 𝑛 ∈ ℕ∗ , 𝑛 ≥ 4.
Suponemos cierto que se cumple para 𝑛 = 𝑘 (hipótesis de inducción): 2𝑘 < 𝑘! 𝐻𝐼 Lo cual ha de implicar que se cumplirá para 𝑛 = 𝑘 + 1 , es decir: Lo verificamos: 2𝑘+1 < (𝑘 + 1)! (𝑘 + 1)! = 𝑘! · (𝑘 + 1) Y dado que para 𝑘 ∈ ℕ, 𝑘 ≥ 4 se verifica que 𝑘 + 1 > 2 ⟺ 𝑘 − 1 > 0 , vemos que: 2𝑘+1 = 2𝑘 · 2 < 𝑘! · 2 < 𝑘! · (𝑘 + 1) = (𝑘 + 1)! ∎ Lo demostraremos por inducción. Verificamos 𝑛 = 1 1+𝑟 = 1 − 𝑟2 ⟺ (1 + 𝑟)(1 − 𝑟) = 1 − 𝑟 2 ⟺ 1 − 𝑟 2 = 1 − 𝑟 2 1−𝑟 Suponemos que se cumple para 𝑛 = 𝑘 − 1 (hipótesis de inducción): 1 + 𝑟1 + ⋯ + 𝑟 𝑘−1 = Implicará que se cumple para 𝑛 = 𝑘. Es decir: 1 + 𝑟1 + ⋯ + 𝑟 𝑘 = 1 − 𝑟𝑘 𝐻𝐼 1−𝑟 1 − 𝑟 𝑘+1 1−𝑟 Desarrollaos lado izquierdo teniendo en cuenta la hipótesis de inducción: 1 + 𝑟1 + ⋯ + 𝑟 𝑘 = 1 + 𝑟1 + ⋯ + 𝑟 𝑘−1 + 𝑟 𝑘 = = 1 − 𝑟𝑘 �1 − 𝑟 𝑘 � + 𝑟 𝑘 · (1 − 𝑟) + 𝑟𝑘 = = 1−𝑟 1−𝑟 1 − 𝑟 𝑘 + 𝑟 𝑘 − 𝑟 𝑘+1 1 − 𝑟 𝑘+1 = ∎ 1−𝑟 1−𝑟 7.Demostreu ∀ n ∈ N∗ el seg¨ uent resultat: n n k n−k x y k (x + y)n = k=0 n k on = def n! k!(n−k)! 1) Veiem que ´es cert per a n = 1: 1 k=0 1 k 1 0 xk y 1−k = 1 1 x0 y 1 + x1 y 0 = y + x = (x + y)1 2) Suposem-ho cert per a n: n k=0 n k n−k x y = (x + y)n k 3) Veiem que ´es cert per a n + 1: n (x + y)n+1 = (x + y)(x + y)n = (x + y) k=0 n x k=0 n k n−k x y k n + y k=0 n k n−k x y k n = k=0 n k n−k x y = k n k+1 n−k x y + k n k=0 n k n+1−k x y = k (en el primer sumatori fem el canvi k = k + 1 i del segon treiem el terme per k = 0) n+1 n “ ” “n” X „ n « X n = xk y n+1−k + xk y n+1−k + x0 y n+1 = k −1 k 0 k=1 k =1 (ara en el primer sumatori treiem el terme per k = n + 1) « n „ n “ ” “n” “n” X X n n = xk y n+1−k + xn+1 y 0 + xk y n+1−k + x0 y n+1 = k −1 n k 0 k=1 k =1 (finalment en el primer sumatori fem k = k i l’agrupem amb el segon) « “ ”– n »„ “n” “n” X n n =(∗) xk y n+1−k + xn+1 y 0 + x0 y n+1 = + n 0 k − 1 k k=1 « „ « „ « n „ X n+1 n+1 n+1 = xk y n+1−k + xn+1 y 0 + x0 y n+1 = k n + 1 0 k=1 n+1 X „n + 1« = xk y n+1−k k k=0 (∗): Justificaci´ o que `n´ k + “ n k−1 ” = “ n+1 k ” : recordar que 0! = 1 “n” „ n « n! n! n! n! + = + = + = k!(n − k)! (k − 1)!(n − k + 1)! k(k − 1)!(n − k)! (k − 1)!(n + 1 − k)(n − k)! k k−1 „ « n!(n + 1 − k) + n!k n!(n + 1) (n + 1)! n+1 = = = = k(n − k)!(k − 1)!(n − k + 1) k!(n + 1 − k)! k!(n + 1 − k)! k 1The end ...