Diferencia entre revisiones de «Inducción matemática»
Contenido eliminado Contenido añadido
Intento de mejorar concordancia. |
Añadir algunas variantes de inducción |
||
Línea 4:
:Dado un número entero <math>a\,</math> que tiene la [[propiedad (lógica)|propiedad]] <math>P\,</math>, y el hecho de que si hasta cualquier número entero <math>n\,</math> con la propiedad <math>P\,</math> [[implicación|implique]] que <math>n+1\,</math> también la tiene, entonces, ''todos'' los números enteros a partir de <math>a\,</math> tienen la propiedad <math>P\,</math>.
:
La demostración está basada en el [[axioma]] denominado ''principio de la inducción matemática''.<ref>"Diccionario de Matemáticas" de Christopher Clapham (1998) ISBN 84-89784-56-6</ref>{{cita|La inducción matemática demuestra que podemos subir tan alto como queramos en una escalera, si demostramos que podemos subir el primer peldaño (el "caso base") y que desde cada peldaño podemos subir al siguiente (el "paso" inductivo).|''[[Concrete Mathematics]]'', pág. 3, margen (en inglés).|col2=}}
== Historia ==
Línea 90 ⟶ 91:
::<math>\sum_{k=1}^{h+1} (2k - 1) 3^k = h 3^{h+2} + 3</math>
:Por lo tanto, verificándose la proposición para <math>n=1</math> y para <math>n=k+1</math> siendo <math>k </math> cualquier número natural, la proposición se verifica <math>\forall n \in \mathbb {N}</math>.
== Variantes ==
En la práctica, las demostraciones por inducción se estructuran a menudo de manera diferente, dependiendo de la naturaleza exacta de la propiedad a demostrar.
=== Caso base distinto de 0 o 1 ===
Si se desea demostrar una afirmación no para todos los números naturales sino sólo para todos los números ''n'' mayores o iguales a un cierto número ''b'', entonces la prueba por inducción consiste en:
# Mostrando que la afirmación es válida cuando ''n'' = ''b''
# Mostrando que si la afirmación es válida para algunos {{nowrap|''n'' ≥ ''b''}} entonces la misma declaración también es válida para {{nowrap|''n'' + ''1''}}.
Esto puede usarse, por ejemplo, para mostrar que {{nowrap|2<sup>''n''</sup> ≥ ''n'' + 5}} para {{nowrap|''n ≥ 3}}.''
De esta manera, se puede probar que alguna declaración ''P''(''n'') es válida para todos ''n'' ≥ 1, o incluso ''n'' ≥ -5. Esta forma de inducción matemática es en realidad un caso especial de la forma anterior, porque si la declaración a probar es ''P''(''n'') entonces probarla con estas dos reglas es equivalente a probar ''P'(''n'' + ''b'') para todos los números naturales'' n''' con un caso base de inducción 0.<ref>Ted Sundstrom, "Mathematical Reasoning", pág. 190, (en inglés), Pearson, 2006, ISBN 978-013187718184</ref>.'''
=== Inducción en más de un contador ===
A veces se requiere demostrar una afirmación que involucra dos números naturales, ''n'' y ''m'', mediante la repetición del proceso de inducción. Esto es, uno prueba un caso base y un paso inductivo para ''n'', y en cada uno de ellos prueba un caso base y un paso inductivo para ''m''. También son posibles argumentos más complicados que involucren tres o más contadores.
=== Descenso infinito ===
El método del descenso infinito es una variación de la inducción matemática que fue utilizada por [[Pierre de Fermat]]. Se utiliza para mostrar que alguna afirmación ''Q''(''n'') es falsa para todos los números naturales ''n''. Su forma tradicional consiste en mostrar que si ''Q''(''n'') es cierto para algún número natural ''n'', también lo es para algún número natural ''m''' estrictamente más pequeño. Debido a que no hay secuencias infinitas de números naturales que disminuyan, esta situación sería imposible, mostrando por contradicción que la ''Q''(''n'') no puede ser cierta para ninguna ''n''.
La validez de este método puede ser verificada desde el principio habitual de la inducción matemática. Usando inducción matemática en la declaración ''P''(''n'') definida como "''Q''(''m'') es falsa para todos los números naturales ''m'' menos que o igual a ''n''", se deduce que ''P''(''n'') es válida para todos ''n'', lo que significa que ''Q''(''n'') es falsa para todos los números naturales ''n''.
=== Inducción fuerte ===
Otra variante, llamada "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'').
== La propiedad del buen orden ==
| |||