Inducción matemática
Una técnica reversa, contando regresivamente en lugar de ascendentemente, se puede encontrar en la paradoja sorites, en donde se argumenta que si 1 000 000 de granos de arena forman un montón y removiendo un grano del montón a la vez, este sigue siendo un montón, entonces, hasta un solo grano (incluso ningún grano de arena) formaría un montón.
Ninguno de estos antiguos matemáticos explicitó la hipótesis inductiva.
Otro caso similar fue el de Francesco Maurlico en su Arithmeticorom libri duo (1575), que usó la técnica para probar que la suma de los n primeros enteros impares es igual a n al cuadrado.
La primera formulación explícita sobre el principio de inducción fue establecida por el filósofo y matemático Blaise Pascal en su obra Traité du triangle arithmétique (1665).
[2] Otro francés, Fermat, hace amplio uso de un principio relacionado para una demostración indirecta del descenso infinito.
La hipótesis inductiva fue también empleada por el suizo Jakob Bernoulli y a partir de entonces fue más conocida.
El tratamiento de carácter riguroso y sistemático llega solo en el siglo XIX d. C. con George Boole, Augustus De Morgan, Charles Sanders Peirce, Giuseppe Peano y Richard Dedekind.
La inducción puede empezar por otro término que no sea
Se probará que la siguiente declaración P (n), que se supone válida para todos los números naturales n. P (n) da una fórmula para la suma de los números naturales menores o igual a n. La prueba de que P (n) es verdadera para todos los números naturales procede como sigue.
Base: Se muestra que es válida para n = 1. con P(1) se tiene: En el lado izquierdo de la ecuación, el único término es 1, entonces su valor es 1. mientras que el término derecho, 1·(1 + 1)/2 = 1.
Puesto que se han realizado los dos pasos de la inducción matemática tanto la base como el paso inductivo, la declaración P(n) se cumple para todo número natural
La demostración está basada en el axioma denominado principio de la inducción matemática.
Si se desea demostrar una afirmación no para todos los números naturales sino solo para todos los números n mayores o iguales a un cierto número b, entonces la prueba por inducción consiste en: Esto puede usarse, por ejemplo, para mostrar que 2n ≥ n + 5 para n ≥ 3.
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.
[4] 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.
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. 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 P(m + 1) bajo la suposición de que P(n) se cumple para cualquier número natural n menor que m + 1; por el contrario, la forma básica solo 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.
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.
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 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).
Para este ejemplo se puede partir de lo siguiente: Sea
Todo conjunto de enteros no negativos tiene un elemento mínimo.
A menudo se utiliza esta propiedad directamente en las demostraciones.
[5] Usa la propiedad del buen orden para demostrar el algoritmo de la división, recuerda que el algoritmo de la división dice que si a es un número entero y d es un entero positivo, entonces hay dos únicos enteros c y r tales que 0
d y a = dc + r. Solución: Sea S el conjunto de los enteros no negativos de la forma a-dc, donde c es un entero.
Este conjunto no es vacío, porque como vemos -dc se puede agrandar tanto como queramos, eso si, tomando c como un número entero que no sea negativo con un valor absoluto que sea grande, por la propiedad del buen orden, S tiene mínimo un elemento r=a-dc0.
d, de no ser así, habría un número que no sería negativo menor en S. Por lo tanto, existen los enteros c y r', 0
