Diferencia entre revisiones de «Inducción matemática»
Contenido eliminado Contenido añadido
m Mantenimiento de Control de autoridades |
|||
Línea 117:
=== Inducción fuerte ===
Otra variante, llamada "[[Inducción fuerte|inducción fuerte]]" (en contraste con la forma básica de inducción que a veces se conoce como "inducción débil") hace que el paso inductivo sea más fácil de demostrar utilizando una hipótesis más fuerte: uno prueba la afirmación {{nowrap|''P''(''m'' + 1)}} bajo la suposición de que ''P''(''n'') se cumple para ''cualquier'' número natural ''n'' menor que {{nowrap|''m'' + 1}}; por el contrario, la forma básica sólo asume ''P''(''m''). El nombre "inducción fuerte" no significa que este método pueda probar más que "inducción débil", sino que simplemente se refiere a la hipótesis más fuerte utilizada en la etapa inductiva; de hecho, los dos métodos son equivalentes, como se explica más adelante. En esta forma de inducción completa todavía hay que probar el caso base, ''P''(0), e incluso puede ser necesario probar casos base adicionales como ''P''(1) antes de que se aplique el argumento general, como en el caso de los números de Fibonacci ''F<sub>n</sub>'''.
La inducción fuerte es equivalente a la inducción matemática ordinaria descrita anteriormente, en el sentido de que una demostración por un método puede transformarse en una demostración por el otro. Supongamos que hay una prueba de ''P'' (''n'') por inducción completa. Que Q(''n'') signifique "''P''(''m'') se cumple para todos ''m'' tal que {{nowrap|0 ≤ ''m'' ≤ ''n''}}". Entonces Q(''n'') se cumple para cualquier ''n'' si y sólo si P(''n'') se mantiene para cualquier ''n'', y nuestra demostración de ''P''(''n'') se transforma fácilmente en una demostración de Q(''n''') por inducción (ordinaria). Si, por otro lado, ''P''(''n'') hubiera sido demostrado por inducción ordinaria, la prueba ya sería efectivamente una por inducción completa: ''P''(0) se prueba en el caso base, sin usar suposiciones, y {{nowrap|''P''(''n'' + 1)}} se prueba en la etapa inductiva, en la que se pueden asumir todos los casos anteriores, pero sólo se necesita usar el caso ''P''(''n'').
| |||