Inducción Fuerte

Inducción Fuerte

por MICHELINI SOFIA -
Número de respostas: 3

Buenas tardes!

Quisiera saber si me pueden explicar quizá a modo de ejemplo o lo que crean mejor la diferencia entre inducción completa y fuerte.

Desde ya muchas gracias.

Em resposta à MICHELINI SOFIA

Re: Inducción Fuerte

por FORETS MARCELO -
El concepto de "inducción completa débil" o simplemente "inducción débil" es el que vimos desde la primera clase con la analogía del dominó, es decir la ficha n-ésima tira a la ficha (n+1)-ésima.

Por otro lado, el concepto de "inducción completa fuerte" o simplemente "inducción fuerte" sería un juego en el que para tirar la ficha (n+1)-ésima no sólo hace falta que caiga la n-ésima, sino también todas (o parte de) las anteriores. De ahí es donde viene lo de "fuerte", fuerte en el sentido de que se piden condiciones adicionales a la condición n-ésima.
Em resposta à MICHELINI SOFIA

Re: Inducción Fuerte

por TORNARIA GONZALO -
Te sugiero que des una leída al Teorema 4.2 en la página 196 del Grimaldi, y lo que sigue. En particular, el ejemplo 4.12 lo hicimos en clase y hay uno parecido en el práctico.

La diferencia esencial es que en la demostración del paso inductivo tenés derecho a utilizar como hipótesis no solamente el paso anterior, sino cualquiera de los anteriores.

Esto se ve en la demostración del ejemplo 4.12, cuando vas a probar el paso inductivo (la explicación comienza al principio de la página 198), para probar la tesis inductiva S'(k+1) utilizas como hipótesis inductiva que valen S'(k), S'(k-1) y S'(k-2).

A cambio de esta conveniencia, tienes que ser más cuidadosa con la demostración del paso base. En este ejemplo 4.12 verás que Grimaldi prueba 3 casos como paso base: S'(0), S'(1) y S'(2).