b'\n_START_ARTICLE_\nInducci\xc3\xb3n matem\xc3\xa1tica\n_START_SECTION_\nHistoria\n_START_PARAGRAPH_\nEn el Parmenides, de Plat\xc3\xb3n del 370 a.C, quiz\xc3\xa1 se puede identificar un temprano ejemplo de una explicaci\xc3\xb3n impl\xc3\xadcita de prueba inductiva. La m\xc3\xa1s antigua huella de la inducci\xc3\xb3n matem\xc3\xa1tica se puede encontrar en la demostraci\xc3\xb3n de Euclides en el s.\xc2\xa0III\xc2\xa0a.\xc2\xa0C. sobre la infinitud de los n\xc3\xbameros primos y en la de Bhaskara I usando su \xc2\xabm\xc3\xa9todo c\xc3\xadclico\xc2\xbb._NEWLINE_Una t\xc3\xa9cnica 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\xc3\xb3n y removiendo un grano del mont\xc3\xb3n a la vez, este sigue siendo un mont\xc3\xb3n, entonces, hasta un solo grano (incluso ning\xc3\xban grano de arena) formar\xc3\xada un mont\xc3\xb3n._NEWLINE_Una demostraci\xc3\xb3n impl\xc3\xadcita de la inducci\xc3\xb3n matem\xc3\xa1tica para secuencias aritm\xc3\xa9ticas fue introducida por Al-Karaji en su obra Al-Fakhri escrita alrededor de 1000 d. C., usado para probar el teorema del binomio y las propiedades del tri\xc3\xa1ngulo de Pascal._NEWLINE_Ninguno de estos antiguos matem\xc3\xa1ticos explicit\xc3\xb3 la hip\xc3\xb3tesis inductiva. Otro caso similar fue el de Francesco Maurlico en su Arithmeticorom libri duo (1575), que us\xc3\xb3 la t\xc3\xa9cnica para probar que la suma de los n primeros enteros impares es igual a n al cuadrado._NEWLINE_La primera formulaci\xc3\xb3n expl\xc3\xadcita sobre el principio de inducci\xc3\xb3n fue establecida por el fil\xc3\xb3sofo y matem\xc3\xa1tico Blaise Pascal en su obra Trait\xc3\xa9 du triangle arithm\xc3\xa9tique (1665).\xe2\x80\x8b Otro franc\xc3\xa9s, Fermat, hace amplio uso de un principio relacionado para una demostraci\xc3\xb3n indirecta del descenso infinito. La hip\xc3\xb3tesis inductiva fue tambi\xc3\xa9n empleada por el suizo Jakob Bernoulli y a partir de entonces fue m\xc3\xa1s conocida._NEWLINE_El tratamiento de car\xc3\xa1cter riguroso y sistem\xc3\xa1tico llega solo en el siglo\xc2\xa0XIX\xc2\xa0d.\xc2\xa0C. con George Boole, Augustus De Morgan, Charles Sanders Peirce, Giuseppe Peano y Richard Dedekind.\n_START_SECTION_\nVariantes\n_START_PARAGRAPH_\nEn la pr\xc3\xa1ctica, las demostraciones por inducci\xc3\xb3n se estructuran a menudo de manera diferente, dependiendo de la naturaleza exacta de la propiedad a demostrar.\n_START_SECTION_\nInducci\xc3\xb3n en m\xc3\xa1s de un contador\n_START_PARAGRAPH_\nA veces se requiere demostrar una afirmaci\xc3\xb3n que involucra dos n\xc3\xbameros naturales, n y m, mediante la repetici\xc3\xb3n del proceso de inducci\xc3\xb3n. 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\xc3\xa9n son posibles argumentos m\xc3\xa1s complicados que involucren tres o m\xc3\xa1s contadores.\n_START_SECTION_\nDescenso infinito\n_START_PARAGRAPH_\nEl m\xc3\xa9todo del descenso infinito es una variaci\xc3\xb3n de la inducci\xc3\xb3n matem\xc3\xa1tica que fue utilizada por Pierre de Fermat. Se utiliza para mostrar que alguna afirmaci\xc3\xb3n Q(n) es falsa para todos los n\xc3\xbameros naturales n. Su forma tradicional consiste en mostrar que si Q(n) es cierto para alg\xc3\xban n\xc3\xbamero natural n, tambi\xc3\xa9n lo es para alg\xc3\xban n\xc3\xbamero natural m\' estrictamente m\xc3\xa1s peque\xc3\xb1o. Debido a que no hay secuencias infinitas de n\xc3\xbameros naturales que disminuyan, esta situaci\xc3\xb3n ser\xc3\xada imposible, mostrando por contradicci\xc3\xb3n que la Q(n) no puede ser cierta para ninguna n. _NEWLINE_La validez de este m\xc3\xa9todo puede ser verificada desde el principio habitual de la inducci\xc3\xb3n matem\xc3\xa1tica.  Usando inducci\xc3\xb3n matem\xc3\xa1tica en la declaraci\xc3\xb3n P(n) definida como "Q(m) es falsa para todos los n\xc3\xbameros naturales m menos que o igual a n", se deduce que P(n) es v\xc3\xa1lida para todos n, lo que significa que Q(n) es falsa para todos los n\xc3\xbameros naturales n.\n_START_SECTION_\nInducci\xc3\xb3n fuerte\n_START_PARAGRAPH_\nOtra variante, llamada "inducci\xc3\xb3n fuerte" (en contraste con la forma b\xc3\xa1sica de inducci\xc3\xb3n que a veces se conoce como "inducci\xc3\xb3n d\xc3\xa9bil") hace que el paso inductivo sea m\xc3\xa1s f\xc3\xa1cil de demostrar utilizando una hip\xc3\xb3tesis m\xc3\xa1s fuerte: uno prueba la afirmaci\xc3\xb3n P(m + 1) bajo la suposici\xc3\xb3n de que P(n) se cumple para cualquier n\xc3\xbamero natural n menor que m + 1; por el contrario, la forma b\xc3\xa1sica s\xc3\xb3lo asume P(m). El nombre "inducci\xc3\xb3n fuerte" no significa que este m\xc3\xa9todo pueda probar m\xc3\xa1s que "inducci\xc3\xb3n d\xc3\xa9bil", sino que simplemente se refiere a la hip\xc3\xb3tesis m\xc3\xa1s fuerte utilizada en la etapa inductiva; de hecho, los dos m\xc3\xa9todos son equivalentes, como se explica m\xc3\xa1s adelante. En esta forma de inducci\xc3\xb3n completa todav\xc3\xada 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\xc3\xbameros de Fibonacci F\xe2\x82\x99\'._NEWLINE_La inducci\xc3\xb3n fuerte es equivalente a la inducci\xc3\xb3n matem\xc3\xa1tica ordinaria descrita anteriormente, en el sentido de que una demostraci\xc3\xb3n por un m\xc3\xa9todo puede transformarse en una demostraci\xc3\xb3n por el otro. Supongamos que hay una prueba de P (n) por inducci\xc3\xb3n completa. Que Q(n) signifique "P(m) se cumple para todos m tal que 0 \xe2\x89\xa4 m \xe2\x89\xa4 n".  Entonces Q(n) se cumple para cualquier n si y s\xc3\xb3lo si P(n) se mantiene para cualquier n, y nuestra demostraci\xc3\xb3n de P(n) se transforma f\xc3\xa1cilmente en una demostraci\xc3\xb3n de Q(n\') por inducci\xc3\xb3n (ordinaria). Si, por otro lado, P(n) hubiera sido demostrado por inducci\xc3\xb3n ordinaria, la prueba ya ser\xc3\xada efectivamente una por inducci\xc3\xb3n 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\xc3\xb3lo se necesita usar el caso P(n).\n_START_SECTION_\nLa propiedad del buen orden\n_START_PARAGRAPH_\nLa validez de la inducci\xc3\xb3n matem\xc3\xa1tica est\xc3\xa1 basada en el principio de buena ordenaci\xc3\xb3n de los conjuntos de n\xc3\xbameros enteros no negativos._NEWLINE_Todo conjunto de enteros no negativos tiene un elemento m\xc3\xadnimo._NEWLINE_A menudo se utiliza esta propiedad directamente en las demostraciones. _NEWLINE_\xe2\x80\x8b\n_START_SECTION_\nEjemplo\n_START_PARAGRAPH_\nUsa la propiedad del buen orden para demostrar el algoritmo de la divisi\xc3\xb3n, recuerda que el algoritmo de la divisi\xc3\xb3n dice que si a es un n\xc3\xbamero entero y d es un entero positivo, entonces hay dos \xc3\xbanicos enteros c y r tales que 0rd y a=dc+r._NEWLINE_Soluci\xc3\xb3n: Sea S el conjunto de los enteros no negativos de la forma a-dc, donde c es un entero. Este conjunto no es vac\xc3\xado, porque como vemos -dc se puede agrandar tanto como queramos, eso si, tomando c como un n\xc3\xbamero entero que no sea negativo con un valor absoluto que sea grande, por la propiedad del buen orden, S tiene m\xc3\xadnimo un elemento r=a-dc\xe2\x82\x80._NEWLINE_El entero r no puede ser negativo, tambi\xc3\xa9n imaginamos que rd, de no ser as\xc3\xad, habr\xc3\xada un n\xc3\xbamero que no ser\xc3\xada negativo menor en S. Por lo tanto, existen los enteros c y r\', 0rd.'