Principio de inducción

En matemáticas, la inducción es un razonamiento que permite demostrar proposiciones que dependen de una variable ${displaystyle n,}$ que toma una infinidad de valores enteros. En términos simples, la inducción matemática consiste en el siguiente razonamiento:

La demostración está basada en el axioma denominado principio de la inducción matemática.^[1]​

En el Parmenides, de Platón del 370 a.C, quizá se puede identificar un temprano ejemplo de una explicación implícita de prueba inductiva. La más antigua huella de la inducción matemática se puede encontrar en la demostración de Euclides en el s. III a. C. sobre la infinitud de los números primos y en la de Bhaskara I usando su «método cíclico».

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.

Una demostración implícita de la inducción matemática para secuencias aritméticas 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ángulo de Pascal.

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.

Llamemos ${displaystyle P_{n},}$ a la proposición, donde ${displaystyle n,}$ es el rango.

Luego, demostrado esto, concluimos por inducción, que ${displaystyle P_{n},}$ es cierto para todo natural ${displaystyle n,}$.

La inducción puede empezar por otro término que no sea ${displaystyle P_{1},}$, digamos por ${displaystyle P_{n_{0}},}$. Entonces ${displaystyle P_{n},}$ será válido a partir del número ${displaystyle n_{0},}$, es decir, para todo natural ${displaystyle ngeq n_{0},}$.

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.
Ambos lados son iguales, n = 1. Entonces P(1) es verdadera.

Paso inductivo: Mostrar que si P(k) es verdadera, entonces P(k + 1) es verdadera. Como sigue:

Se asume que P(k) es verdadera (para un valor no específico de k). Se debe entonces mostrar que P(k + 1) es verdadera:

usando la hipótesis de inducción P(k) es verdadera, el término izquierdo se puede reescribir:

Desarrollando:

mostrando de hecho que P(k + 1) es verdadera.

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 ${displaystyle n}$ Q.E.D.

Como resultado obtenemos:

${displaystyle left(a+b ight)^{n}=sum _{k=0}^{n}{n choose k}left(a ight)^{k}left(b ight)^{n-k}=sum _{k=0}^{n+1}{n+1 choose k}a^{k}b^{(n+1)-k}}$

La demostración está basada en el axioma denominado principio de la inducción matemática.^[3]​

Propuesta: Demostrar que todo número mayor o igual a 7 es suma de un múltiplo de 3 y un múltiplo de 4.

Se demuestra que la afirmación es cierta en el primer caso. 7 es suma de un múltiplo de 3 y un múltiplo de 4, ya que ${displaystyle 7=1*3+1*4}$

Se supone que la afirmación es cierta para un n y se debe mostrar que entonces es cierta para n+1.

n es suma de un múltiplo de 3 y un múltiplo de 4.

Si ${displaystyle n=3r+4s}$, entonces, ${displaystyle (n+1)=3r+4s+1}$ y se necesita ver si esto es la suma un múltiplo de 3 y uno de 4. Efectivamente, se cumple que:

Como la afirmación es cierta para un número n dicha afirmación será cierta para un número n+1

Propuesta: Demostrar que ${displaystyle n!>2^{n}}$ para toda ${displaystyle ngeq 4}$

${displaystyle 4!=24}$ y ${displaystyle 2^{4}=16}$, por tanto, ${displaystyle 4!>2^{4}}$

Se parte de que ${displaystyle n!>2^{n}}$. Se debe demostrar que ${displaystyle (n+1)!>2^{(n+1)}}$

Como ${displaystyle ngeq 4Leftrightarrow (n+1)geq 5}$ , por tanto, ${displaystyle 2^{n}(n+1)geq 2^{n}(5)>2^{n}(2)=2^{n+1}}$.

Finalmente: ${displaystyle (n+1)!>2^{n+1}}$

Se debe demostrar que ${displaystyle 1cdot 2cdot 3cdot 4cdot cdot cdot n>2^{n}}$

Para n = 4, ${displaystyle 1cdot 2cdot 3cdot 4cdot cdot cdot n>2^{4}Leftrightarrow 24>16}$

A pesar de que la afirmación se cumple para n = 4, para n = 1, n = 2 y n = 3 no se cumple la afirmación.

Entonces, si descartamos estos valores, el trabajo a realizar es demostrar ${displaystyle 1cdot 2cdot 3cdot 4cdot cdot cdot n>2^{n}}$ para ${displaystyle ngeq 4}$

Para demostrar que la desigualdad es válida para k+1, es decir ${displaystyle 1cdot 2cdot 3cdot 4cdot cdot cdot n(n+1)>2^{n+1}}$ para ${displaystyle ngeq 4}$

${displaystyle 1cdot 2cdot 3cdot 4cdot cdot cdot n(n+1)=(1cdot 2cdot 3cdot 4cdot cdot cdot n(n+1)>2^{n}(n+1)>2^{n}cdot 2=2^{n+1}}$

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.

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 2ⁿ ≥ n + 5 para 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.^[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.

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.

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, 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_n'.

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 0 ≤ m ≤ n". Entonces Q(n) se cumple para cualquier n si y solo 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 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 ${displaystyle varphi }$ una proposición de los naturales tal que para todo m en los naturales y para todo k menor que m se cumple que ${displaystyle varphi (k)=>varphi (m)}$, entonces, para todo n en los naturales, ${displaystyle varphi (n)}$ es cierto.

Expresándolo de forma matemática:

${displaystyle forall min mathbb {N} }$ ( [${displaystyle forall k<m}$ ${displaystyle varphi (k)}$] ${displaystyle Rightarrow varphi (m)}$ ) ${displaystyle Rightarrow forall nin mathbb {N} }$ ${displaystyle varphi (n)}$.

Empleando el principio del buen orden:

Por ende, se ha llegado a la conclusión de que A no tiene mínimo => ${displaystyle A=varnothing }$

La validez de la inducción matemática está basada en el principio de buena ordenación de los conjuntos de números enteros no negativos.

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${displaystyle leq }$r${displaystyle leq }$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-dc₀.

El entero r no puede ser negativo, también imaginamos que r${displaystyle leq }$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${displaystyle leq }$r${displaystyle leq }$d.

---