Inducción matemática

La inducción matemática es un método para demostrar que una afirmación es verdadera. $P(n)$ Esto es cierto para cada número natural. $n$ , es decir, que los infinitos casos $P(0),P(1),P(2),P(3),\dots$ Todas las afirmaciones son válidas. Esto se logra demostrando primero un caso sencillo y luego mostrando que, si asumimos que la afirmación es verdadera para un caso dado, entonces el siguiente caso también lo es. Las metáforas informales ayudan a explicar esta técnica, como la caída de fichas de dominó o subir una escalera:

La inducción matemática prueba que podemos subir tan alto como queramos en una escalera, demostrando que podemos subir al peldaño inferior (la base ) y que desde cada peldaño podemos subir al siguiente (el escalón ).

— Matemáticas Concretas , página 3, márgenes.

Una demostración por inducción consta de dos casos. El primero, el caso base , demuestra la afirmación para $n=0$ sin asumir ningún conocimiento de otros casos. El segundo caso, el paso de inducción , demuestra que si la afirmación se cumple para cualquier caso dado $n=k$ , entonces también debe cumplirse para el siguiente caso. $n=k+1$ Estos dos pasos establecen que la afirmación se cumple para cada número natural. $n$ . El caso base no necesariamente comienza con $n=0$ pero a menudo con $n=1$ y posiblemente con cualquier número natural fijo $n=N$ , estableciendo la veracidad de la afirmación para todos los números naturales. $n\geq N$ .

El método puede extenderse para demostrar afirmaciones sobre estructuras bien fundamentadas más generales , como los árboles ; esta generalización, conocida como inducción estructural , se utiliza en lógica matemática e informática . La inducción matemática en este sentido extendido está estrechamente relacionada con la recursión . La inducción matemática es una regla de inferencia utilizada en demostraciones formales y es la base de la mayoría de las pruebas de corrección de programas informáticos. ^{[ 3 ]}

A pesar de su nombre, la inducción matemática difiere fundamentalmente del razonamiento inductivo utilizado en filosofía , en el que el examen de muchos casos conduce a una conclusión probable. El método matemático examina infinitos casos para demostrar una afirmación general, pero lo hace mediante una cadena finita de razonamiento deductivo que involucra la variable. $n$ , que puede tomar infinitos valores. El resultado es una prueba rigurosa de la afirmación, no una aseveración de su probabilidad. ^{[ 4 ]}

Historia

Según David E. Joyce , no hay evidencia del uso del principio de inducción matemática en los escritos de Euclides . ^{[ 5 ]} Acerbi (2000) argumenta que el Parménides de Platón (c. 370 a. C.) contiene rastros de una prueba inductiva implícita temprana. ^{[ 6 ]} Esta interpretación ha sido cuestionada por Negrepontis y Farmaki (2021), quienes afirman además que ni Platón ni ninguno de los otros pitagóricos utilizaron el principio de inducción matemática. ^{[ 7 ]}

La primera demostración implícita por inducción matemática fue escrita por al-Karaji alrededor del año 1000 d. C., quien la aplicó a sucesiones aritméticas para demostrar el teorema del binomio y las propiedades del triángulo de Pascal . Si bien la obra original se perdió, posteriormente fue citada por Al-Samawal al-Maghribi en su tratado al-Bahir fi'l-jabr (El brillante en álgebra) alrededor del año 1150 d. C. ^{[ 8 ]}^{[ 9 ]}^{[ 10 ]}

Katz dice en su historia de las matemáticas

Otra idea importante introducida por al-Karaji y continuada por al-Samaw'al y otros fue la de un argumento inductivo para tratar ciertas secuencias aritméticas. Así, al-Karaji utilizó dicho argumento para demostrar el resultado sobre las sumas de cubos enteros que ya conocía Aryabhata [...] Sin embargo, al-Karaji no enunció un resultado general para un n arbitrario . Enunció su teorema para el entero particular 10 [...] Su demostración, no obstante, estaba claramente diseñada para ser extensible a cualquier otro entero. [...] El argumento de al-Karaji incluye, en esencia, los dos componentes básicos de un argumento moderno por inducción, a saber, la verdad de la afirmación para n = 1 (1 = 1/3 ⁾ y la derivación de la verdad para n = k a partir de la de n = k − 1. Por supuesto, este segundo componente no es explícito ya que, en cierto sentido, el argumento de al-Karaji es inverso; es decir, parte de n = 10 y desciende hasta 1 en lugar de proceder hacia arriba. Sin embargo, su argumento en al-Fakhri es la prueba más antigua existente de la fórmula de suma para cubos enteros . ^{[ 11 ]}

En India, las primeras demostraciones implícitas por inducción matemática aparecen en el " método cíclico " de Bhaskara . ^[¹²^]

Sin embargo, ninguno de estos matemáticos antiguos enunció explícitamente la hipótesis de inducción. Otro caso similar (contrario a lo que escribió Vacca, como demostró cuidadosamente Freudenthal) ^{[ 13 ]} fue el de Francesco Maurolico en su Arithmeticorum libri duo (1575), quien utilizó la técnica para demostrar que la suma de los primeros $n$ enteros impares es $n² .$

El primer uso riguroso de la inducción fue realizado por Gersonides (1288–1344). ^{[ 14 ]}^{[ 15 ]} La primera formulación explícita del principio de inducción fue dada por Pascal en su Traité du triangle arithmétique (1665). Otro francés, Fermat , hizo un amplio uso de un principio relacionado: la prueba indirecta por descenso infinito .

La hipótesis de inducción también fue empleada por el suizo Jakob Bernoulli , y desde entonces se hizo muy conocida. El tratamiento formal moderno del principio llegó recién en el siglo XIX, con George Boole , ^{[ 16 ]} Augustus De Morgan , Charles Sanders Peirce , ^{[ 17 ]}^{[ 18 ]} Giuseppe Peano y Richard Dedekind . ^{[ 12 ]}

Descripción

La forma más simple y común de inducción matemática infiere que una afirmación que involucra un número natural $n$ (es decir, un entero $n \geq 0$ o 1) se cumple para todos los valores de $n$ . La demostración consta de dos pasos:

Elcaso base (ocaso inicial): demuestre que la afirmación se cumple para 0 o 1.
ElPaso de inducción (opaso inductivo, ocaso de paso): demostrar que para cada $n$ , si la afirmación se cumple para $n$ , entonces se cumple para $n + 1.$ En otras palabras, suponer que la afirmación se cumple para algún número natural arbitrario $n$ , y demostrar que la afirmación se cumple para $n + 1$ .

La hipótesis en el paso de inducción, que establece que la afirmación se cumple para un $n$ particular , se denomina hipótesis de inducción o hipótesis inductiva . Para demostrar el paso de inducción, se asume la hipótesis de inducción para $n$ y luego se utiliza esta suposición para probar que la afirmación se cumple para $n + 1$ .

Los autores que prefieren definir los números naturales comenzando en 0 usan ese valor en el caso base; aquellos que los definen comenzando en 1 usan ese valor.

Ejemplos

Suma de números naturales consecutivos

La inducción matemática puede utilizarse para demostrar la siguiente afirmación para todos los números naturales. $n\geq 0$ : $P(n)\!:\ \ 0+1+2+\cdots +n={\frac {n(n+1)}{2}}.$

Esto establece una fórmula general para la suma de los números naturales menores o iguales a un número dado; de hecho, una secuencia infinita de enunciados: $0={\tfrac {(0)(0+1)}{2}}$ , $0+1={\tfrac {(1)(1+1)}{2}}$ , $0+1+2={\tfrac {(2)(2+1)}{2}}$ , etc.

Proposición. Para cada $n\in \mathbb {N}$ , tenemos eso $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$

Prueba. Dejemos $P(n)$ ser la declaración $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$ Damos una demostración por inducción sobre $n$ .

Caso base: Demuestre que la afirmación se cumple para el número natural más pequeño $n = 0$ .

$P(0)$ Es claramente cierto: $0={\tfrac {0(0+1)}{2}}\,.$

Paso de inducción: Demuestre que para cada $k\geq 0$ , si $P(k)$ sostiene, entonces $P(k+1)$ También se sostiene.

Supongamos la hipótesis de inducción de que para un caso particular $k$ , el único caso $n=k$ sostiene, lo que significa $P(k)$ es cierto: $0+1+\cdots +k={\frac {k(k+1)}{2}}.$ Resulta que: $(0+1+2+\cdots +k)+(k+1)={\frac {k(k+1)}{2}}+(k+1).$

Algebraicamente , el lado derecho se simplifica como: ${\begin{aligned}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)}{2}}.\end{aligned}}$

Igualando los extremos izquierdo y derecho, deducimos que: $0+1+2+\cdots +k+(k+1)={\frac {(k+1)((k+1)+1)}{2}}.$ Es decir, la declaración $P(k+1)$ Esto también es cierto, estableciendo el paso de inducción.

Conclusión: Dado que tanto el caso base como el paso de inducción han sido demostrados como verdaderos, por inducción matemática la afirmación $P(n)$ se cumple para cada número natural $n\geq 0$ QED

Una desigualdad trigonométrica

La inducción se usa a menudo para demostrar desigualdades . Como ejemplo, demostramos que $\left|\sin nx\right|\leq n\left|\sin x\right|$ para cualquier número real $x$ y número natural $n$ .

A primera vista, puede parecer que una versión más general, $\left|\sin nx\right|\leq n\left|\sin x\right|$ para cualquier número real $n,x$ , podría probarse sin inducción; pero el caso ${\textstyle n={\frac {1}{2}},\,x=\pi }$ muestra que puede ser falso para valores no enteros de $n$ . Esto sugiere que examinemos la afirmación específicamente para valores naturales de $n$ y la inducción es la herramienta más adecuada.

Proposición. Para cualquier $x\in \mathbb {R}$ y $n\in \mathbb {N}$ , $\left|\sin nx\right|\leq n\left|\sin x\right|$ .

Demostración. Fijemos un número real arbitrario. $x$ y dejar $P(n)$ ser la declaración $\left|\sin nx\right|\leq n\left|\sin x\right|$ . Iniciamos en $n$ .

Caso base: El cálculo $\left|\sin 0x\right|=0\leq 0=0\left|\sin x\right|$ verifica $P(0)$ .

Paso de inducción: Mostramos la implicación $P(k)\implies P(k+1)$ para cualquier número natural $k$ . Supongamos la hipótesis de inducción: para un valor dado $n=k\geq 0$ , el único caso $P(k)$ Es cierto. Usando la fórmula de suma de ángulos y la desigualdad triangular , deducimos: ${\begin{aligned}\left|\sin(k+1)x\right|&=\left|\sin kx\cos x+\sin x\cos kx\right|&&{\text{(angle addition)}}\\&\leq \left|\sin kx\cos x\right|+\left|\sin x\,\cos kx\right|&&{\text{(triangle inequality)}}\\&=\left|\sin kx\right|\left|\cos x\right|+\left|\sin x\right|\left|\cos kx\right|\\&\leq \left|\sin kx\right|+\left|\sin x\right|&&(\left|\cos t\right|\leq 1)\\&\leq k\left|\sin x\right|+\left|\sin x\right|&&{\text{(induction hypothesis}})\\&=(k+1)\left|\sin x\right|.\end{aligned}}$

La desigualdad entre las cantidades de los extremos izquierdo y derecho muestra que $P(k+1)$ es cierto, lo que completa el paso de inducción.

Conclusión: La proposición $P(n)$ Esto se cumple para todos los números naturales. $n.$ QED

Variantes

En la práctica, las demostraciones por inducción suelen estructurarse de forma diferente, dependiendo de la naturaleza exacta de la propiedad que se pretende demostrar. Todas las variantes de inducción son casos especiales de inducción transfinita ; véase más abajo .

Caso base distinto de 0 o 1

Si uno 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 demostración por inducción consiste en lo siguiente:

Demostrando que la afirmación se cumple cuando $n = b$ .
Demostrando que si la afirmación es válida para un número arbitrario $n \geq b$ , entonces la misma afirmación también es válida para $n + 1$ .

Esto se puede utilizar, por ejemplo, para demostrar que $2 n \geq n + 5$ para $n \geq 3$ .

De esta forma, se puede demostrar que una proposición $P (n)$ se cumple para todo $n \geq 1$ , o incluso para todo $n \geq -5$ . Esta forma de inducción matemática es en realidad un caso especial de la forma anterior, porque si la proposición que se pretende demostrar es $P (n),$ ^entonces demostrarla con estas dos reglas equivale a demostrar $P (n + b)$ para todos los números naturales $n$ con un caso base de inducción $0.$ [ ^{19 ]}

Ejemplo: formar cantidades de dólares con monedas

Supongamos una cantidad infinita de monedas de 4 y 5 dólares. La inducción permite demostrar que cualquier cantidad entera de dólares mayor o igual a $12$ se puede formar mediante la combinación de dichas monedas. Sea $S (k)$ la proposición " $k$ dólares se pueden formar mediante la combinación de monedas de 4 y 5 dólares". La demostración de que $S (k)$ es verdadera para todo $k \geq 12$ se puede obtener mediante inducción sobre $k$ de la siguiente manera:

Caso base: Demostrar que $S (k)$ se cumple para $k = 12$ es sencillo: tome tres monedas de 4 dólares.

Paso de inducción: Dado que $S (k)$ se cumple para algún valor de $k \geq 12$ ( hipótesis de inducción ), demuestre que $S (k + 1)$ también se cumple. Suponga que $S (k)$ es verdadera para algún $k \geq 12$ arbitrario . Si existe una solución para $k$ dólares que incluya al menos una moneda de 4 dólares, reemplácela por una moneda de 5 dólares para obtener $k + 1$ dólares. De lo contrario, si solo se usan monedas de 5 dólares, $k$ debe ser un múltiplo de 5 y, por lo tanto, al menos 15; pero entonces podemos reemplazar tres monedas de 5 dólares por cuatro monedas de 4 dólares para obtener $k + 1$ dólares. En cada caso, $S (k + 1)$ es verdadera.

Por lo tanto, por el principio de inducción, $S (k)$ se cumple para todo $k \geq 12$ , y la demostración está completa.

En este ejemplo, aunque $S (k)$ también se cumple para ${\textstyle k\in \{4,5,8,9,10\}}$ , la demostración anterior no se puede modificar para reemplazar la cantidad mínima de $12$ dólares por ningún valor $m$ menor . Para $m = 11$ , el caso base es realmente falso; para $m = 10$ , el segundo caso en el paso de inducción (reemplazar tres monedas de 5 dólares por cuatro monedas de 4 dólares) no funcionará; y mucho menos para valores de $m$ aún menores .

Inducción en más de un mostrador

En ocasiones, resulta conveniente demostrar una proposición que involucra dos números naturales, $n$ y $m$ , mediante la iteración del proceso de inducción. Es decir, se demuestra un caso base y un paso de inducción para $n$ , y en cada uno de estos casos se demuestra un caso base y un paso de inducción para $m$ . Véase, por ejemplo, la demostración de la conmutatividad que acompaña a la suma de números naturales . También son posibles argumentos más complejos que involucran tres o más contadores.

Descenso infinito

El método del descenso infinito es una variación de la inducción matemática utilizada por Pierre de Fermat . Se emplea para demostrar que una proposición $Q (n)$ es falsa para todos los números naturales $n$ . Su forma tradicional consiste en demostrar que si $Q (n)$ es verdadera para algún número natural $n$ , también lo es para algún número natural $m$ estrictamente menor . Dado que no existen sucesiones decrecientes infinitas de números naturales, esta situación sería imposible, demostrando así ( por contradicción ) que $Q (n)$ no puede ser verdadera para ningún $n$ .

La validez de este método se puede verificar a partir del principio habitual de inducción matemática. Usando la inducción matemática sobre la afirmación $P (n)$ definida como " $Q (m)$ es falsa para todos los números naturales $m$ menores o iguales a $n$ ", se deduce que $P (n)$ se cumple para todo $n$ , lo que significa que $Q (n)$ es falsa para todo número natural $n$ .

Inducción matemática limitada

Si se desea demostrar que una propiedad $P$ se cumple para todos los números naturales menores o iguales a un $N$ fijo , basta con demostrar que $P$ satisface las siguientes condiciones: ^{[ 20 ]}

$P$ se cumple para 0,
Para cualquier número natural $x$ menor que $N$ , si $P$ se cumple para $x$ , entonces $P$ se cumple para $x + 1.$

Inducción de prefijos

La forma más común de demostración por inducción matemática requiere probar en el paso de inducción que $\forall k\,(P(k)\to P(k+1))$

En consecuencia, el principio de inducción "automatiza" $n$ aplicaciones de este paso para pasar de $P (0)$ a $P (n)$ . Esto podría denominarse "inducción predecesora" porque cada paso demuestra algo sobre un número a partir de algo sobre su predecesor.

Una variante de interés en complejidad computacional es la "inducción de prefijos", en la que se demuestra la siguiente afirmación en el paso de inducción: $\forall k\,(P(k)\to P(2k)\land P(2k+1))$ o equivalentemente $\forall k\,\left(P\!\left(\left\lfloor {\frac {k}{2}}\right\rfloor \right)\to P(k)\right)$

El principio de inducción automatiza entonces log₂ _n aplicaciones de esta inferencia para pasar de $P$ $(0)$ a $P$ $($ $n$ $)$ . De hecho, se denomina «inducción de prefijos» porque cada paso demuestra algo sobre un número a partir de algo sobre el «prefijo» de ese número, formado al truncar el bit menos significativo de su representación binaria . También puede considerarse una aplicación de la inducción tradicional sobre la longitud de dicha representación binaria.

Si la inducción tradicional por predecesor se interpreta computacionalmente como un bucle $de n$ pasos, entonces la inducción por prefijo correspondería a un bucle de log $-n$ pasos. Por ello, las demostraciones que utilizan la inducción por prefijo son "más factiblemente constructivas" que las que utilizan la inducción por predecesor.

La inducción de predecesores puede simular trivialmente la inducción de prefijos en la misma proposición. La inducción de prefijos puede simular la inducción de predecesores, pero solo a costa de hacer la proposición más compleja sintácticamente (añadiendo un cuantificador universal acotado ), por lo que los resultados interesantes que relacionan la inducción de prefijos con la computación en tiempo polinomial dependen de excluir por completo los cuantificadores no acotados y limitar la alternancia de cuantificadores universales y existenciales acotados permitidos en la proposición. ^[²¹^]

Se puede llevar la idea un paso más allá: hay que demostrar $\forall k\,\left(P\!\left(\left\lfloor {\sqrt {k}}\right\rfloor \right)\to P(k)\right)$ En consecuencia, el principio de inducción "automatiza" $log log n$ aplicaciones de esta inferencia para pasar de $P (0)$ a $P (n)$ . Esta forma de inducción se ha utilizado, de forma análoga, para estudiar la computación paralela en tiempo logarítmico.

Inducción completa (fuerte)

Otra variante, llamada inducción completa , inducción de curso de valores o inducción fuerte (en contraste con la cual la forma básica de inducción a veces se conoce como inducción débil ), hace que el paso de inducción sea más fácil de probar al usar una hipótesis más fuerte: se prueba la afirmación $P(m+1)$ bajo el supuesto de que $P(n)$ Esto se cumple para todos los números naturales. $n$ menos 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 demostrar más que la "inducción débil", sino que simplemente se refiere a la hipótesis más fuerte utilizada en el paso de inducción.

De hecho, se puede demostrar que los dos métodos son realmente equivalentes, como se explica a continuación. En esta forma de inducción completa, todavía hay que demostrar el caso base, $P(0)$ y puede incluso ser necesario demostrar casos extrabase como $P(1)$ antes de que se aplique el argumento general, como en el ejemplo siguiente del número de Fibonacci $F_{n}$ .

Aunque la forma que se acaba de describir requiere que uno demuestre el caso base, esto es innecesario si uno puede demostrar $P(m)$ (arrogante $P(n)$ para todos los inferiores $n$ ) para todos $m\geq 0$ Este es un caso especial de inducción transfinita como se describe a continuación, aunque ya no es equivalente a la inducción ordinaria. En esta forma, el caso base está subsumido por el caso $m=0$ , dónde $P(0)$ se demuestra sin ningún otro $P(n)$ supuesto; este caso puede necesitar ser tratado por separado, pero a veces se aplica el mismo argumento para $m=0$ y $m>0$ , haciendo que la demostración sea más simple y elegante. Sin embargo, en este método es vital asegurar que la demostración de $P(m)$ no asume implícitamente que $m>0$ , por ejemplo, diciendo "elige un arbitrario $n<m$ ", o asumiendo que un conjunto de $m$ elementos tiene un elemento.

Equivalencia con la inducción ordinaria

La inducción completa 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 existe una demostración de $P(n)$ por inducción completa. Entonces, esta demostración puede transformarse en una demostración de inducción ordinaria asumiendo una hipótesis inductiva más fuerte. Sea $Q(n)$ ser la declaración " $P(m)$ se aplica a todos $m$ de tal manera que $0\leq m\leq n$ "—esta se convierte en la hipótesis inductiva para la inducción ordinaria. Entonces podemos demostrar $Q(0)$ y $Q(n+1)$ para $n\in \mathbb {N}$ suponiendo que solo $Q(n)$ y demostrar que $Q(n)$ implica $P(n)$ . ^{[ 22 ]}

Si, por otro lado, $P(n)$ Si se hubiera demostrado mediante inducción ordinaria, la prueba sería ya, en efecto, una prueba por inducción completa: $P(0)$ se demuestra en el caso base, sin utilizar supuestos, y $P(n+1)$ se demuestra en el paso de inducción, en el que se pueden asumir todos los casos anteriores pero solo es necesario utilizar el caso $P(n)$ .

Ejemplo: Números de Fibonacci

La inducción completa es más útil cuando se requieren varias instancias de la hipótesis inductiva para cada paso de la inducción. Por ejemplo, la inducción completa se puede utilizar para demostrar que $F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}$ dónde $F_{n}$ es el $n$ -ésimo número de Fibonacci y ${\textstyle \varphi ={\frac {1}{2}}(1+{\sqrt {5}})}$ (la proporción áurea ) y ${\textstyle \psi ={\frac {1}{2}}(1-{\sqrt {5}})}$ son las raíces del polinomio $x^{2}-x-1$ . Utilizando el hecho de que $F_{n+2}=F_{n+1}+F_{n}$ para cada $n\in \mathbb {N}$ , la identidad anterior puede verificarse mediante cálculo directo para ${\textstyle F_{n+2}}$ si se asume que ya se cumple para ambos ${\textstyle F_{n+1}}$ y ${\textstyle F_{n}}$ Para completar la prueba, la identidad debe verificarse en los dos casos base: $n=0$ y ${\textstyle n=1}$ .

Ejemplo: factorización prima

Otra demostración por inducción completa utiliza la hipótesis de que la afirmación se cumple para todos los valores más pequeños. $n$ con más detalle. Consideremos la afirmación de que "todo número natural mayor que 1 es producto de (uno o más) números primos ", que es la parte de " existencia " del teorema fundamental de la aritmética . Para demostrar el paso de inducción, la hipótesis de inducción es que para un dado $m>1$ La afirmación es válida para todos los más pequeños. $n>1$ . Si $m$ Si es primo, entonces ciertamente es un producto de primos, y si no, entonces por definición es un producto: $m=n_{1}n_{2}$ donde ninguno de los factores es igual a 1; por lo tanto, ninguno es igual a $m$ y por lo tanto ambos son mayores que 1 y menores que $m$ La hipótesis de inducción ahora se aplica a $n_{1}$ y $n_{2}$ , por lo que cada uno es un producto de números primos. Así pues $m$ es un producto de productos de números primos y, por lo tanto, por extensión, un producto de números primos en sí mismo.

Ejemplo: importes en dólares revisados

Intentaremos demostrar el mismo ejemplo anterior , esta vez con inducción fuerte . La afirmación sigue siendo la misma: $S(n):\,\,n\geq 12\implies \,\exists \,a,b\in \mathbb {N} .\,\,n=4a+5b$

Sin embargo, habrá ligeras diferencias en la estructura y las suposiciones de la demostración, comenzando con el caso base extendido.

Prueba.

Caso base: Demuestre que $S(k)$ se mantiene para $k=12,13,14,15$ . ${\begin{aligned}4\cdot 3+5\cdot 0=12\\4\cdot 2+5\cdot 1=13\\4\cdot 1+5\cdot 2=14\\4\cdot 0+5\cdot 3=15\end{aligned}}$

El caso base se mantiene.

Paso de inducción: Dado algún $j>15$ , asumir $S(m)$ se aplica a todos $m$ con $12\leq m<j$ Demuestra que $S(j)$ sostiene.

Elegir $m=j-4$ y observando que $15<j\implies 12\leq j-4<j$ muestra que $S(j-4)$ se sostiene, por la hipótesis inductiva. Es decir, la suma $j-4$ puede formarse mediante alguna combinación de $4$ y $5$ monedas de dólar. Luego, simplemente agregando una $4$ una moneda de dólar a esa combinación produce la suma $j$ . Eso es, $S(j)$ se sostiene. ^{[ 23 ]} QED

Inducción hacia adelante y hacia atrás

A veces, es más conveniente deducir hacia atrás, demostrando la afirmación para $n-1$ , dada su validez para $n$ Sin embargo, demostrar la validez de la afirmación para ningún número individual es suficiente para establecer el caso base; en cambio, es necesario demostrar la afirmación para un subconjunto infinito de los números naturales. Por ejemplo, Augustin Louis Cauchy primero utilizó la inducción directa (regular) para demostrar la desigualdad de las medias aritmética y geométrica para todas las potencias de 2 , y luego utilizó la inducción inversa para demostrarla para todos los números naturales. ^{[ 24 ]}^{[ 25 ]}

Ejemplo de error en el paso de inducción

El paso de inducción debe probarse para todos los valores de $n$ . Para ilustrar esto, Joel E. Cohen propuso el siguiente argumento, que pretende probar por inducción matemática que todos los caballos son del mismo color : ^{[ 26 ]}

Caso base: en un conjunto de un solo caballo, solo hay un color.

Paso de inducción: asumir como hipótesis de inducción que dentro de cualquier conjunto de $n$ caballos, solo hay un color. Ahora mira cualquier conjunto de $n+1$ caballos. Numéralos: $1,2,3,\dotsc ,n,n+1$ Consideremos los conjuntos ${\textstyle \left\{1,2,3,\dotsc ,n\right\}}$ y ${\textstyle \left\{2,3,4,\dotsc ,n+1\right\}}$ Cada uno es un conjunto de solo $n$ caballos, por lo tanto, dentro de cada uno hay solo un color. Pero los dos conjuntos se superponen, por lo que debe haber solo un color entre todos. $n+1$ caballos.

El caso base $n=1$ es trivial y el paso de inducción es correcto en todos los casos. $n>1$ Sin embargo, el argumento utilizado en el paso de inducción es incorrecto para $n+1=2$ , porque la afirmación de que "los dos conjuntos se superponen" es falsa para ${\textstyle \left\{1\right\}}$ y ${\textstyle \left\{2\right\}}$ .

Formalización

En lógica de segundo orden , el " axioma de inducción" se puede escribir de la siguiente manera: $\forall P\,{\Bigl (}P(0)\land \forall k{\bigl (}P(k)\to P(k+1){\bigr )}\to \forall n\,{\bigl (}P(n){\bigr )}{\Bigr )},$ donde $P (\cdot)$ es una variable para predicados que involucran un número natural y $k$ y $n$ son variables para números naturales .

En otras palabras, el caso base $P (0)$ y el paso de inducción (es decir, que la hipótesis de inducción $P (k)$ implica $P (k + 1)$ ) implican conjuntamente que $P (n)$ se cumple para cualquier número natural $n$ . El axioma de inducción afirma la validez de inferir que $P (n)$ se cumple para cualquier número natural $n$ a partir del caso base y el paso de inducción.

El primer cuantificador del axioma abarca predicados en lugar de números individuales. Se trata de un cuantificador de segundo orden, lo que significa que este axioma se formula en lógica de segundo orden . La axiomatización de la inducción aritmética en lógica de primer orden requiere un esquema axiomático que contenga un axioma independiente para cada predicado posible. El artículo «Axiomas de Peano» ofrece un análisis más detallado de este tema.

El axioma de inducción estructural para los números naturales fue formulado por primera vez por Peano, quien lo utilizó para especificar los números naturales junto con los siguientes cuatro axiomas:

0 es un número natural.
La función sucesora $s$ de cada número natural produce un número natural $(s (x) = x + 1)$ .
La función sucesora es inyectiva .
0 no está en el rango de $s$ .

En la teoría de conjuntos ZFC de primer orden , la cuantificación sobre predicados no está permitida, pero aún se puede expresar la inducción mediante cuantificación sobre conjuntos: $\forall A{\Bigl (}0\in A\land \forall k\in \mathbb {N} {\bigl (}k\in A\to (k+1)\in A{\bigr )}\to \mathbb {N} \subseteq A{\Bigr )}$ $A$ puede interpretarse como un conjunto que representa una proposición y contiene números naturales para los cuales se cumple dicha proposición. Esto no es un axioma, sino un teorema, dado que los números naturales se definen en el lenguaje de la teoría de conjuntos ZFC mediante axiomas, análogos a los de Peano. Véase la construcción de los números naturales utilizando el axioma del infinito y el esquema de especificación de axiomas .

Inducción transfinita

Una variante del principio de inducción completa puede generalizarse para afirmaciones sobre elementos de cualquier conjunto bien fundado , es decir, un conjunto con una relación irreflexiva < que no contiene cadenas descendentes infinitas . Todo conjunto que representa un número ordinal es bien fundado; el conjunto de los números naturales es uno de ellos.

Aplicada a un conjunto bien fundamentado, la inducción transfinita puede formularse como un solo paso. Para demostrar que una afirmación $P (n)$ se cumple para cada número ordinal:

Demuestre, para cada número ordinal $n$ , que si $P (m)$ se cumple para todo $m < n$ , entonces $P (n)$ también se cumple.

Esta forma de inducción, cuando se aplica a un conjunto de números ordinales (que forman una clase bien ordenada y, por lo tanto, bien fundamentada ), se denomina inducción transfinita . Es una técnica de demostración importante en teoría de conjuntos , topología y otros campos.

Las demostraciones por inducción transfinita suelen distinguir tres casos:

cuando $n$ es un elemento mínimo, es decir, no hay ningún elemento menor que $n$ ;
cuando $n$ tiene un predecesor directo, es decir, el conjunto de elementos que son menores que $n$ tiene un elemento mayor;
cuando $n$ no tiene un predecesor directo, es decir, $n$ es un llamado ordinal límite .

En rigor, en inducción transfinita no es necesario demostrar un caso base, ya que se trata de un caso particular trivial de la proposición de que si $P$ es verdadera para todo $n < m$ , entonces $P$ es verdadera para $m$ . Es trivial precisamente porque no existen valores de $n < m$ que puedan servir como contraejemplos. Por lo tanto, los casos particulares son casos particulares del caso general.

Relación con el principio de buen ordenamiento

El principio de inducción matemática se suele enunciar como un axioma de los números naturales; véanse los axiomas de Peano . Es estrictamente más fuerte que el principio de buen orden en el contexto de los demás axiomas de Peano. Supongamos lo siguiente:

El axioma de la tricotomía : Para cualesquiera números naturales $n$ y $m$ , $n$ es menor o igual que $m$ si y solo si $m$ no es menor que $n$ .
Para cualquier número natural $n$ , $n + 1$ es mayor que n .
Para cualquier número natural $n$ , ningún número natural está entre n y $n + 1$ .
Ningún número natural es menor que cero.

Se puede demostrar entonces que la inducción, dados los axiomas mencionados anteriormente, implica el principio de buen ordenamiento. La siguiente demostración utiliza la inducción completa y el primer y cuarto axioma.

Demostración. Supongamos que existe un conjunto no vacío , $S$ , de números naturales que no tiene un elemento mínimo. Sea $P (n)$ la afirmación de que $n$ no pertenece a $S.$ Entonces $P (0)$ es verdadera, pues si fuera falsa, 0 sería el elemento mínimo de $S.$ Además, sea $n$ un número natural y supongamos que $P (m)$ es verdadera para todos los números naturales $m$ menores que $n + 1.$ Entonces, si $P (n + 1)$ es falsa $, n + 1$ pertenece a $S$ , siendo así un elemento mínimo en $S$ , lo cual es una contradicción. Por lo tanto, $P (n + 1$ ) es verdadera. En consecuencia, por el principio de inducción completa, $P (n)$ se cumple para todos los números naturales $n$ ; por lo tanto , $S$ es vacío, lo cual es una contradicción. QED

" Recta numérica " para el conjunto

{(0, n): n \in N} \cup {(1, n): n \in N}

. Los números se refieren al segundo componente de los pares; el primero se puede obtener a partir del color o la ubicación.

Por otro lado, el conjunto $\{(0,n):n\in \mathbb {N} \}\cup \{(1,n):n\in \mathbb {N} \}$ , mostrado en la imagen, está bien ordenado ^{[ 27 ]}^{: 35lf} por el orden lexicográfico . Además, excepto por el axioma de inducción, satisface todos los axiomas de Peano, donde la constante 0 de Peano se interpreta como el par (0, 0), y la función sucesora de Peano se define en pares por $succ(x, n) = (x, n + 1)$ para todo $x\in \{0,1\}$ y $n\in \mathbb {N}$ Como ejemplo de la violación del axioma de inducción, definamos el predicado $P (x, n)$ como $(x, n) = (0, 0)$ o $(x, n) = succ(y, m)$ para algún $y\in \{0,1\}$ y $m\in \mathbb {N}$ Entonces, el caso base $P (0, 0)$ es trivialmente verdadero, y también lo es el paso de inducción: si $P (x, n)$ , entonces $P (succ(x, n))$ . Sin embargo, $P$ no es verdadero para todos los pares del conjunto, ya que $P (1,0)$ es falso.

Los axiomas de Peano, junto con el principio de inducción, modelan de forma única los números naturales. Reemplazar el principio de inducción por el principio de buen orden permite obtener modelos más exóticos que cumplen con todos los axiomas. ^{[ 27 ]}

^{En varios libros [ 27 ]} y fuentes se imprime erróneamente que el principio de buen ordenamiento es equivalente al axioma de inducción. En el contexto de los demás axiomas de Peano, esto no es así, pero en el contexto de otros axiomas, son equivalentes; ^{[ 27 ]} específicamente, el principio de buen ordenamiento implica el axioma de inducción en el contexto de los dos primeros axiomas enumerados anteriormente y

Todo número natural es 0 o $n + 1$ para algún número natural $n$ .

Un error común en muchas demostraciones erróneas es suponer que $n - 1$ es un número natural único y bien definido, una propiedad que no está implícita en los demás axiomas de Peano. ^{[ 27 ]}

Véase también

Notas

↑ Matt DeVos, Inducción matemática , Universidad Simon Fraser
↑ Gerardo con Díaz, Inducción matemática. Archivado el 2 de mayo de 2013 en Wayback Machine , Universidad de Harvard.
↑ Anderson, Robert B. (1979). Demostrando la corrección de programas . Nueva York: John Wiley & Sons. pág . 1. ISBN 978-0471033950.
↑ Suber, Peter. "Inducción matemática" . Earlham College. Archivado del original el 24 de mayo de 2011. Recuperado el 26 de marzo de 2011 .
↑ "Elementos de Euclides, Libro VII, Definiciones 1 y 2" . webspace.ship.edu . Consultado el 23 de mayo de 2026 .
↑ Acerbi, Fabio (1 de enero de 2000). "Platón: Parménides 149a7-c3. ¿Una demostración por inducción completa?" . Archivo de Historia de las Ciencias Exactas 55 (2000), 57–76 .
↑ Sriraman, Bharath, ed. (2024), Handbook of the history and philosophy of mathematical practice. Volume 4, Springer nature reference, Cham: Springer, p. 985, ISBN 978-3-031-40845-8, leyendo las fuentes meticulosamente, tenemos algunos argumentos novedosos que muestran que los pitagóricos tenían de hecho una prueba inductiva, pero sin el principio de inducción matemática.
↑ Rashed 1994 , págs. 62–84.
↑ Conocimiento matemático y la interacción de las prácticas : "La primera demostración implícita por inducción matemática se dio alrededor del año 1000 en una obra del matemático persa Al-Karaji".
↑ "El teorema del binomio" . mathcenter.oxford.emory.edu . Consultado el 2 de diciembre de 2024. Dicho esto, no fue la primera persona en estudiarlo. Actualmente se le atribuye su descubrimiento al matemático e ingeniero persa Al-Karaji, que vivió entre 935 y 1029. ( Dato curioso: Al-Karaji también introdujo la poderosa idea de argumentar por inducción matemática ) .
↑ Katz (1998), pág. 255
1 2 Cajori (1918) , p. 197: «El proceso de razonamiento llamado “inducción matemática” ha tenido varios orígenes independientes. Se remonta al suizo Jakob (James) Bernoulli, a los franceses B. Pascal y P. Fermat, y al italiano F. Maurolycus. [...] Leyendo entre líneas se pueden encontrar rastros de inducción matemática aún más antiguos, en los escritos de los hindúes y los griegos, como, por ejemplo, en el “método cíclico” de Bhaskara y en la demostración de Euclides de que el número de primos es infinito».
↑ Rashed 1994 , pág. 62.
↑ Simonson 2000 .
↑ Rabinovitch 1970 .
↑ "A veces se requiere demostrar un teorema que será verdadero siempre que una cierta cantidad n involucrada sea un número entero, y el método de demostración suele ser del siguiente tipo: 1. Se demuestra que el teorema es verdadero cuando n = 1. 2. Se demuestra que si el teorema es verdadero cuando n es un número entero dado, también lo será si n es el siguiente entero mayor. Por lo tanto, el teorema es verdadero universalmente. … Este tipo de argumento puede denominarse sorites continuado " (Boole c. 1849, Tratado elemental de lógica, no matemático, pp. 40-41, reimpreso en Grattan-Guinness, Ivor y Bornet, Gérard (1997), George Boole: Manuscritos selectos sobre lógica y su filosofía , Birkhäuser Verlag, Berlín, ISBN 3-7643-5456-9)
↑ Peirce 1881 .
↑ Shields 1997 .
↑ Ted Sundstrom, Razonamiento matemático , pág. 190, Pearson, 2006, ISBN 978-0131877184
↑ Smullyan, Raymond (2014). Guía para principiantes de lógica matemática . Dover. pág. 41. ISBN 978-0486492377.
↑ Buss, Samuel (1986). Aritmética acotada . Nápoles: Bibliopolis.
↑ "Demostración: La inducción fuerte es equivalente a la inducción débil" . Universidad de Cornell . Consultado el 4 de mayo de 2023 .
↑ Shafiei, Niloufar. "Inducción fuerte y buen ordenamiento" (PDF) . Universidad de York . Consultado el 28 de mayo de 2023 .
↑ "Inducción hacia adelante y hacia atrás | Brilliant Math & Science Wiki" . brilliant.org . Consultado el 23 de octubre de 2019 .
↑ Cauchy, Augustin-Louis (1821). Cours d'analyse de l'École Royale Polytechnique, première partie, Analyse algébrique, Archivado el 14 de octubre de 2017 en Wayback Machine París. La demostración de la desigualdad de las medias aritmética y geométrica se encuentra en las páginas 457 y siguientes.
↑ Cohen, Joel E. (1961). "Sobre la naturaleza de la demostración matemática". Opus .Reimpreso en A Random Walk in Science (RL Weber, ed.), Crane, Russak & Co., 1973.
1 2 3 4 5 Öhman, Lars–Daniel (6 de mayo de 2019). "¿Son equivalentes la inducción y el buen ordenamiento?" . The Mathematical Intelligencer . 41 (3): 33– 40. doi : 10.1007/s00283-019-09898-4 .

Referencias

Introducción

Franklin, J.; Daoud, A. (2011). Demostración en matemáticas: Una introducción . Sydney: Kew Books. ISBN 978-0-646-54509-7.(Capítulo 8.)
"Inducción matemática" . Enciclopedia de Matemáticas . EMS Press . 2001 [1994].
Hermes, Hans (1973). Introducción a la lógica matemática . Hochschultext. Londres: Springer. ISBN 978-3540058199. ISSN 1431-4657 . MR 0345788 .
Knuth, Donald E. (1997). El arte de la programación informática, Volumen 1: Algoritmos fundamentales (3.ª ed.). Addison-Wesley. ISBN 978-0-201-89683-1.(Sección 1.2.1: Inducción matemática, págs. 11-21.)
Kolmogorov, Andrey N.; Fomin , Sergei V. (1975). Introducción al análisis real . Silverman, RA (trad., ed.). Nueva York: Dover. ISBN 978-0-486-61226-3.(Sección 3.8: Inducción transfinita, págs. 28-29.)

Historia

Acerbi, Fabio (agosto de 2000). "Platón: Parménides 149a7-c3. ¿Una demostración por inducción completa?" . Archivo para la Historia de las Ciencias Exactas . 55 (1): 57–76 . doi : 10.1007/s004070000020 . JSTOR 41134098. S2CID 123045154 .
Bussey, WH (1917). "El origen de la inducción matemática". The American Mathematical Monthly . 24 (5): 199– 207. doi : 10.2307/2974308 . JSTOR 2974308 .
Cajori, Florian (1918). "Origen del nombre "Inducción matemática"". The American Mathematical Monthly . 25 (5): 197– 201. doi : 10.2307/2972638 . JSTOR 2972638 .
Fowler, D. (1994). "¿Pudieron los griegos haber utilizado la inducción matemática? ¿La utilizaron?". Physis . 31 : 253–265 .
Freudenthal, Hans (1953). "Zur Geschichte der vollständigen Inducción". Archivos Internacionales de Historia de las Ciencias . 6 : 17-37 .
Katz, Victor J. (1998). Historia de las matemáticas: Una introducción . Addison-Wesley . ISBN 0-321-01618-1.
Peirce, Charles Sanders (1881). " Sobre la lógica de los números" . American Journal of Mathematics . 4 ( 1–4 ): 85–95 . doi : 10.2307/2369151 . JSTOR 2369151. MR 1507856 . Reimpreso (CP 3.252–288), (W 4:299–309)
Rabinovitch, Nachum L. (1970). "El rabino Levi Ben Gershon y los orígenes de la inducción matemática". Archivo de Historia de las Ciencias Exactas . 6 (3): 237– 248. doi : 10.1007/BF00327237 . MR 1554128 . S2CID 119948133 .
Rashed, Roshdi (1972). "L'induction mathématique: al-Karajī, as-Samaw'al". Archivo de Historia de las Ciencias Exactas (en francés). 9 (1): 1– 21. doi : 10.1007/BF00348537 . MR 1554160 . S2CID 124040444 .
Rashed, R. (1994). «Inducción matemática: al-Karajī y al-Samawʾal». El desarrollo de las matemáticas árabes: entre la aritmética y el álgebra . Boston Studies in the Philosophy of Science. Vol. 156. Springer Science & Business Media. ISBN 9780792325659.
Shields, Paul (1997). «La axiomatización de la aritmética de Peirce». En Houser, Nathan; Roberts, Don D.; Evra, James Van (eds.). Estudios sobre la lógica de Charles S. Peirce . Indiana University Press. pp. 43–52 . ISBN 0-253-33020-3. MR 1720827 .
Simonson, Charles G. (Invierno de 2000). "Las matemáticas de Levi ben Gershon, el Ralbag" (PDF) . Bekhol Derakhekha Daehu . 10. Bar-Ilan University Press: 5–21 . Archivado del original (PDF) el 11 de octubre de 2017. Recuperado el 29 de diciembre de 2019 .
Unguru, S. (1991). "Matemáticas griegas e inducción matemática". Physis . 28 : 273–289 .
Unguru, S. (1994). "Cazar después de la inducción". Física . 31 : 267–272 .
Vacca, G. (1909). "Maurolycus, el primer descubridor del principio de inducción matemática" . Boletín de la Sociedad Matemática Americana . 16 (2): 70– 73. doi : 10.1090/S0002-9904-1909-01860-9 . MR 1558845 .
Yadegari, Mohammad (1978). "El uso de la inducción matemática por Abū Kāmil Shujā' Ibn Aslam (850-930)". Isis . 69 ( 2): 259– 262. doi : 10.1086/352009 . JSTOR 230435. S2CID 144112534 .

[1] Matt DeVos, Inducción matemática , Universidad Simon Fraser

[2] Gerardo con Díaz, Inducción matemática. Archivado el 2 de mayo de 2013 en Wayback Machine , Universidad de Harvard.

[3] Anderson, Robert B. (1979). Demostrando la corrección de programas . Nueva York: John Wiley & Sons. pág . 1. ISBN 978-0471033950.

[4] Suber, Peter. "Inducción matemática" . Earlham College. Archivado del original el 24 de mayo de 2011. Recuperado el 26 de marzo de 2011 .

[5] "Elementos de Euclides, Libro VII, Definiciones 1 y 2" . webspace.ship.edu . Consultado el 23 de mayo de 2026 .

[6] Acerbi, Fabio (1 de enero de 2000). "Platón: Parménides 149a7-c3. ¿Una demostración por inducción completa?" . Archivo de Historia de las Ciencias Exactas 55 (2000), 57–76 .

[7] Sriraman, Bharath, ed. (2024), Handbook of the history and philosophy of mathematical practice. Volume 4, Springer nature reference, Cham: Springer, p. 985, ISBN 978-3-031-40845-8, leyendo las fuentes meticulosamente, tenemos algunos argumentos novedosos que muestran que los pitagóricos tenían de hecho una prueba inductiva, pero sin el principio de inducción matemática.

[FOOTNOTERashed199462–84-8] Rashed 1994 , págs. 62–84.

[9] Conocimiento matemático y la interacción de las prácticas : "La primera demostración implícita por inducción matemática se dio alrededor del año 1000 en una obra del matemático persa Al-Karaji".

[10] "El teorema del binomio" . mathcenter.oxford.emory.edu . Consultado el 2 de diciembre de 2024. Dicho esto, no fue la primera persona en estudiarlo. Actualmente se le atribuye su descubrimiento al matemático e ingeniero persa Al-Karaji, que vivió entre 935 y 1029. ( Dato curioso: Al-Karaji también introdujo la poderosa idea de argumentar por inducción matemática ) .

[11] Katz (1998), pág. 255

[Induction_Bussey-12] 1 2 Cajori (1918) , p. 197: «El proceso de razonamiento llamado “inducción matemática” ha tenido varios orígenes independientes. Se remonta al suizo Jakob (James) Bernoulli, a los franceses B. Pascal y P. Fermat, y al italiano F. Maurolycus. [...] Leyendo entre líneas se pueden encontrar rastros de inducción matemática aún más antiguos, en los escritos de los hindúes y los griegos, como, por ejemplo, en el “método cíclico” de Bhaskara y en la demostración de Euclides de que el número de primos es infinito».

[FOOTNOTERashed199462-13] Rashed 1994 , pág. 62.

[FOOTNOTESimonson2000-14] Simonson 2000 .

[FOOTNOTERabinovitch1970-15] Rabinovitch 1970 .

[16] "A veces se requiere demostrar un teorema que será verdadero siempre que una cierta cantidad n involucrada sea un número entero, y el método de demostración suele ser del siguiente tipo: 1. Se demuestra que el teorema es verdadero cuando n = 1. 2. Se demuestra que si el teorema es verdadero cuando n es un número entero dado, también lo será si n es el siguiente entero mayor. Por lo tanto, el teorema es verdadero universalmente. … Este tipo de argumento puede denominarse sorites continuado " (Boole c. 1849, Tratado elemental de lógica, no matemático, pp. 40-41, reimpreso en Grattan-Guinness, Ivor y Bornet, Gérard (1997), George Boole: Manuscritos selectos sobre lógica y su filosofía , Birkhäuser Verlag, Berlín, ISBN 3-7643-5456-9)

[FOOTNOTEPeirce1881-17] Peirce 1881 .

[FOOTNOTEShields1997-18] Shields 1997 .

[19] Ted Sundstrom, Razonamiento matemático , pág. 190, Pearson, 2006, ISBN 978-0131877184

[20] Smullyan, Raymond (2014). Guía para principiantes de lógica matemática . Dover. pág. 41. ISBN 978-0486492377.

[Buss:BA-21] Buss, Samuel (1986). Aritmética acotada . Nápoles: Bibliopolis.

[22] "Demostración: La inducción fuerte es equivalente a la inducción débil" . Universidad de Cornell . Consultado el 4 de mayo de 2023 .

[yorku-23] Shafiei, Niloufar. "Inducción fuerte y buen ordenamiento" (PDF) . Universidad de York . Consultado el 28 de mayo de 2023 .

[24] "Inducción hacia adelante y hacia atrás | Brilliant Math & Science Wiki" . brilliant.org . Consultado el 23 de octubre de 2019 .

[25] Cauchy, Augustin-Louis (1821). Cours d'analyse de l'École Royale Polytechnique, première partie, Analyse algébrique, Archivado el 14 de octubre de 2017 en Wayback Machine París. La demostración de la desigualdad de las medias aritmética y geométrica se encuentra en las páginas 457 y siguientes.

[26] Cohen, Joel E. (1961). "Sobre la naturaleza de la demostración matemática". Opus .Reimpreso en A Random Walk in Science (RL Weber, ed.), Crane, Russak & Co., 1973.

[Ohman2019-27] 1 2 3 4 5 Öhman, Lars–Daniel (6 de mayo de 2019). "¿Son equivalentes la inducción y el buen ordenamiento?" . The Mathematical Intelligencer . 41 (3): 33– 40. doi : 10.1007/s00283-019-09898-4 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

entonces

[ 20 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

Historia

Descripción

Ejemplos

Suma de números naturales consecutivos

Una desigualdad trigonométrica

Variantes

Caso base distinto de 0 o 1

Ejemplo: formar cantidades de dólares con monedas

Inducción en más de un mostrador

Descenso infinito

Inducción matemática limitada

Inducción de prefijos

Inducción completa (fuerte)

Equivalencia con la inducción ordinaria

Ejemplo: Números de Fibonacci

Ejemplo: factorización prima

Ejemplo: importes en dólares revisados

Inducción hacia adelante y hacia atrás

Ejemplo de error en el paso de inducción

Formalización

Inducción transfinita

Relación con el principio de buen ordenamiento

Véase también

Notas

Referencias

Introducción

Historia

Articulos relacionados