1AMA0265 Sesión 4.2 ROP - Diagramas de Hasse[Diapo]

UPC – Departamento de Ciencias – MATEMÁTICA DISCRETA (MA265) Profesores MA265 1 Inducción matemática CONTENIDO Unidad 2: LÓGICA Y ALGORITMOS 2.2 Inducción matemática ▪ Introducción ▪ Principio de inducción UPC – Departamento de Ciencias – MATEMÁTICA DISCRETA (MA265) Profesores MA265 2 Inducción Introducción Una gran cantidad de problemas matemáticos pueden ser demostrados simplemente explicando su funcionamiento o lo que significan. Otros son extremadamente difíciles de comprobar; incluso existen ciertas afirmaciones o conjeturas matemáticas aparentemente “sencillas” que aún no se logran demostrar, por ejemplo, la conjetura fuerte de Goldbach. Para facilitar el descubrimiento de nuevas pruebas y demostraciones es importante familiarizarse con algunos estilos estándares de demostración o “argumentación matemática”, como la inducción matemática . La inducción matemática se puede utilizar para analizar y demostrar la correctitud y la eficiencia (complejidad asintótica) de un algoritmo. Generalmente, la aplicación de la inducción en este campo aparece en la literatura como invariantes . Para visualizar la idea de inducción matemática, imagine una colección infinita de fichas de dominó colocadas una detrás de la otra de tal manera que, si alguna ficha de dominó cae hacia atrás, hace que la que está detrás caiga hacia atrás también. Después imagine que la primera ficha de dominó se cae hacia atrás. ¿Qué sucede? . . . ¡Se caen todas! Principio de inducción matemática Sea 𝑃(𝑛) una propiedad que se define para enteros 𝑛 y sea 𝑛 0 un entero fijo. Suponga que los siguientes dos enunciados son verdaderos: 1. 𝑃(𝑛 0 ) es verdadera. 2. Para todo entero 𝑘 ≥ 𝑛 0 , si 𝑃(𝑘) es verdadera entonces 𝑃(𝑘 + 1) es verdadera. Entonces, el enunciado ∀𝑛 ≥ 𝑛 0 , 𝑃(𝑛) es verdadero UPC – Departamento de Ciencias – MATEMÁTICA DISCRETA (MA265) Profesores MA265 3 Ejemplo 1 Se tiene la siguiente declaración 𝑃(𝑛) para todo número natural 𝑛 : 𝑃(𝑛): 1 + 2 + 3 + 4 + ⋯ + 𝑛 = 𝑛(𝑛 + 1) 2 Para demostrar que esto es verdadero para todo 𝑛 natural, se deben seguir los pasos previamente mencionados: • Primero, se demuestra que 𝑷(𝟏) es verdadero 𝑃(1): 1 = 1(1 + 1) 2 𝑃(1): 1 = 1 Nota : En algunos casos, la proposición no se cumple a partir de 1, sino a partir de un número natural 𝑛 0 . Para ello, se debe realizar la demostración de 𝑃(𝑛 0 ) en vez de 𝑃(1) . Como 𝑃(1) es verdadero, continuamos con el segundo paso. A continuación, • Se asume que 𝑷(𝒌) es verdadero , para algún 𝒌 > 𝟏 . De esta forma, al reemplazar en la proposición 𝑛 = 𝑘 en 𝑃(𝑛) tenemos: 𝑃(𝑘): 1 + 2 + 3 + 4 + ⋯ + 𝑘 = 𝑘(𝑘 + 1) 2 Nota : La proposición anterior es conocida como hipótesis inductiva, ya que a partir de dicha proposición se debe demostrar que 𝑷(𝒌 + 𝟏) es verdadero . La forma natural de verificarlo en inducción matemática es convertir 𝑃(𝑘 + 1) en la ecuación de la derecha, a partir de 𝑃(𝑘) , es decir: 𝑃(𝑘 + 1): 1 + 2 + 3 + 4 + ⋯ + 𝑘 + (𝑘 + 1) = (𝑘 + 1)((𝑘 + 1) + 1) 2 Sabemos que 𝑃(𝑘) es verdadero, por tanto: 1 + 2 + 3 + 4 + ⋯ + 𝑘 = 𝑘(𝑘+1) 2 ; luego: 1 + 2 + 3 + 4 + ⋯ + 𝑘 + (𝑘 + 1) = 𝑘(𝑘 + 1) 2 + (𝑘 + 1) = (𝑘 + 1)((𝑘 + 1) + 1) 2 Como 𝑃(𝑘 + 1) resultó igual que la ecuación de la derecha, se demuestra que 𝑃(𝑘 + 1) es verdadero, y, por consiguiente, 𝑃(𝑛) se cumple con todo número natural 𝑛 . Ejemplo 2 Se tiene la siguiente proposición 𝑃(𝑛) para todo número natural 𝑛 : 𝑃(𝑛): 1 + 3 + 5 + ⋯ + (2𝑛 − 1) = 𝑛 2 • Demostraremos que 𝑃(1) es verdadero: UPC – Departamento de Ciencias – MATEMÁTICA DISCRETA (MA265) Profesores MA265 4 𝑃(1): (2 ∗ 1) − 1 = 1 2 • Asumimos que 𝑃(𝑛) es verdadero para 𝑛 = 𝑘 ; por tanto, se tiene que: 𝑃(𝑘): 1 + 3 + 5 + ⋯ + (2𝑘 − 1) = 𝑘 2 Debemos demostrar que 𝑃(𝑘 + 1) es verdadero, es decir: 𝑃(𝑘 + 1): 1 + 3 + 5 + ⋯ + (2(𝑘 + 1) − 1) = (𝑘 + 1) 2 Si le sumamos 2𝑘 + 1 a la igualdad 𝑃(𝑘) en ambos lados obtenemos lo siguiente: 1 + 3 + 5 + ⋯ + (2𝑘 − 1) + (2𝑘 + 1) = 𝑘 2 + (2𝑘 + 1) Agrupando los…