Jazmin · Transcript · · Updated
FC - Práctico 21/08 (inducción fuerte) – Transcript
Video by Jazmin · Watch the original on YouTube
Use this video with Pro
Reading, copying and transcript downloads are free. Create saved AI results for this video with a signed-in Pro account ($9/month).
Transcript
Search ignores accents. All transcript text stays visible.
Ando. Sí. Bien. Entonces, como les decía, eh la idea hoy es trabajar con la parte de inducción fuerte, el práctico.
Entonces, vamos a arcar con este y después eh después vemos. Ya. [carraspeo] Entonces, e sí que no precisan levantar la mano, háblen más.
Ah, yo quería preguntar si eh para la inducción fuerte podés hacer una plantilla como hiciste con inducción completa. [carraspeo] Dale, porque me ayuda me ayuda mucho más a ver los pasos y y hacerlo formal.
Bien de bien. Me parece una buena idea arrancar por ahí. Entonces ahí está. [carraspeo]
Entonces, inusión fuerte azul. Sí, si queres eh más al final mostrás y lo vemos. Sí, sí, pero así me recuerdo porque yo probablemente me olvide porque se me despistada, pero está Si no te digo nada
no es porque no quiero mirarlo, es porque me olvides. Eh, bien. Entonces, ¿cuál es la idea? Mireno que cuando ustedes hacen inducción completa, el paso inductivo, ¿qué es? Supongo que vale para acá y a partir de eso pruebo que vale para AC +s 1. Entonces es como que cuando vos vas a probar la tesis inductiva tenés acceso al caso anterior y punto.
Sí. Entonces, vos tenés principio inducción completa, tenés como vamos a hacer el dibujito de los dominos, suponiendo que empieza en cero, pero puede empezar en cero. Uno tenés K y K + 1. ¿Sí? Entonces, ¿cómo funciona?
Vos hacés tal caso base que como que te tira el primero y después decís, "Bueno, si yo sé que vale para n0, va a valer para n0 + 1." Vamos a poner 5. Entonces, si se verifica para este, está cae este y después dice, "Bueno, yo quiero probar que vale para n0 + 2, ya sé que vale para n0 + 1." Entonces eso
me hace caer. Sí, como que en general si lo quieren probar para acá +s un usan que vale para acá y se olvidan de todo lo anterior, ¿no? Pero en el fondo como si ustedes llegaron a acá es porque lo fueron haciendo caer todos de a uno y entonces no solo es K, que es cierto, es como los anteriores. Sí, pero cuando hacen inducción simple es como que se olvidan de eso. Dicen, "Yo supongo que
vale para acá y uso eso solamente uso este para probar el siguiente." Entonces solamente tengo que si vale para acá entonces p de k + 1 se cumple.
Entonces la diferencia es que en inducción fuerte como que no se olvidan de todo eso. ¿Cómo es la cosa? K K K+ 1. Voy a poner uno más acá.
K men. ¿Qué mejor si estamos haciendo acá, profe? Eh, por ahora ninguna. Yo por las dudas como termin un poco tarde el teórico, ¿no? Por ahora estoy haciendo cuentito más. Eh, sí. Entonces, nción fuerte, ¿qué es? Es no solamente digo que vale para acá.
sino que vale para acá y todos los anteriores. Entonces, lo que usan es como que todo esto es verdadero, entonces agarran toda esa información y hacen caer el camum p de camasum.
¿Sí? Entonces, la diferencia es eso, que en inducción fuerte tienen acceso a mucha más información. No solamente están suponiendo que vale para acá, sino que están suponiendo que vale para acá y para todos los anteriores, ¿ven? Y son son equivalentes porque la inducción completa como que los va haciendo caer de a uno, pero se va olvidando y dice, "Bueno, solo supongo que vale para acá y pruebo que vale para acá más uno." Pero como que si vos
llegaste acá es porque hiciste caer todo lo anterior y cuando haces inducción fuerte no te olvidas de eso. Decí, bueno, voy a como que guardar toda esa información. No solamente vale para acá, sino para acá y para todos los anteriores.
Entonces, esta vamos a escribir cómo era la la plantilla. Entonces, es muy parecido a a la plantilla para la inducción simple,
digamos. Sí. Lo primero que van a hacer es e decir que van a usar inducción fuerte. Entonces, el paso uno es aclarar que vamos a usar el principio de unción fuerte.
Sí. Después lo segundo que van a hacer, que es lo mismo que hacían en inducción simple, es definir bien cuál es la proposición que se va a mostrar.
Después en el paso base, acá la acá Hay otra posible diferencia con inducción simple. Sí, inducción simple hacemos un caso base, ¿no? Probamos que se cumple para el primer natural para el cual se va a cumplir la propiedad. Sí. En inducción fuerte lo que pasa a veces es que tenés que probar más de un caso Sí, después cuando hagamos ejercicios
como que se nota cuando precisas varios casos base o cuando precisas uno solo. Eh, pero a veces como que el costo este de suponer que se cumple para acá y todos los anteriores es que tenes que probar más de un caso base.
Sí. Entonces acá vamos a poner eh probamos, yo que sé, que probar P de N0, P de N0 + 1 y hasta un p sub n1, yo que sé. Sí.
Entonces, dependiendo del ejercicio van a tener que hacer un caso base o dos o tres o algo así. ¿Sí? Entonces está la cantidad de pasos base que tienen que probar eh depende del ejercicio.
Pero me parece que se nota cuántos pasos vas a tenes que hacer. Sí. No es no es una cosa medio oscura. Bien, después del paso base, paso inutivo.
Entonces, acá lo que va a cambiar es la hipótesis indutiva con respecto a indución simple. No solamente vamos a suponer que la proposición se cumple para acá, sino que vamos a suponer que se cumple para acá y para todos para atrás. ¿Sí?
Entonces, suponiendo que se cumplen p de n0, p de n0 + 1, etcétera, bueno, pdn1, pd, ¿sí? O sea, si en el caso base probamos, yo que sé, para cero, para uno y para
dos, entonces en el paso inductivo como que vamos a suponer que se cumple para cero, perdón, a partir de tres, ¿sí? O sea, agarras un k porque los casos bases ya no los incluís acá otra vez.
Sí, entonces agarrás como uno que es por lo menos el N1. supones que se cumple todos los casos base, digamos, y después, bueno, algunos adicionales hasta un PK.
Entonces, suponiendo que se cumplen todos esos, tenemos que probar que se cumple de + 1. Entonces, como siempre, vamos a tener la hipótesis
inductiva, que son las cosas que estamos suponiendo, y la tesis, que es lo que queremos probar. Ahora, la hipótesis inductiva va a ser mucho más fuerte que la inducción simple. Induxo simple era solamente se cumple p, ahora va a ser se cumplen todas estas.
¿Sí? Entonces, vamos a agarrar sea un k mayor o igual que n1. N1 es el último caso base que probamos tal que se cumplen PDN0 PDN0 + 1, PDN1 PNK