Inducción matemática

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

Dado un número entero $a$ que tiene la propiedad $P$, y el hecho de que si hasta cualquier número entero $n$ con la propiedad $P$ implique que $n+1$ también la tiene, entonces, los números enteros a partir de $a$ tienen la propiedad $P$.

Una descripción informal de la inducción matemática puede ser ilustrada por el efecto dominó, donde ocurre una reacción en cadena con una secuencia de piezas de dominó cayendo una detrás de la otra.

La demostración está basada en el axioma denominado principio de la inducción matemática. Plantilla:Cita

Historia

En el Parmenides, de Platón del 370Plantilla:Esda.Plantilla:EsdC., 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 Plantilla:SIGLO 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 1000Plantilla:Esdd. 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). 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 Plantilla:SIGLO con George Boole, Augustus De Morgan, Charles Sanders Peirce, Giuseppe Peano y Richard Dedekind.

Demostraciones por inducción

Llamemos $P_n$ a la proposición, donde $n$ es el rango.

• Base: Se demuestra que $P_1$ es cierta, esto es el primer valor que cumple la proposición (iniciación de la inducción).
• Paso inductivo: Se demuestra que, si $P_n$ es cierta, esto es, como hipótesis inductiva, entonces $P_{n+1}$ lo es también, y esto sin condición sobre el entero natural $n$ (relación de inducción. Indicado como $n\Rightarrow n+1$).

Luego, demostrado esto, concluimos por inducción, que $P_n$ es cierto para todo natural $n$.

La inducción puede empezar por otro término que no sea $P_1$, digamos por $P_{n_0}$. Entonces $P_n$ será válido a partir del número $n_0$, es decir, para todo natural $n\ge n_0$.

Ejemplo 1

Se probará que la siguiente declaración P (n), que se supone válida para todos los números naturales n.

$1+2+\cdots +n=\frac{n(n+1)}{2}.$

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:

$1=\frac{1\cdot (1+1)}{2}.$

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 Plantilla:Nowrap es verdadera. Como sigue:

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

$(1+2+\cdots +k)+(k+1)=\frac{(k+1)((k+1)+1)}{2}.$

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

$\frac{k(k+1)}{2}+(k+1).$

Desarrollando:

$\begin{array}{cc}\frac{k(k+1)}{2}+(k+1)& =\frac{k(k+1)+2(k+1)}{2}\\ & =\frac{k^2+k+2k+2}{2}\\ & =\frac{(k+1)(k+2)}{2}\\ & =\frac{(k+1)((k+1)+1)}{2}\end{array}$

mostrando de hecho que Plantilla:Nowrap 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 $n$ Q.E.D.

Ejemplo 2

Se tratará de demostrar por inducción la siguiente proposición:

$\sum _{k=1}^n(2k-1)3^k=(n-1)3^{n+1}+3$ $\mathrm{\forall }n\in \mathbb{N}$

1. Se comprueba para n=1

$\sum _{k=1}^1(2k-1)3^k=(2\cdot 1-1)3^1=3=(1-1)3^{1+1}+3$

Se tiene por tanto que la proposición es verdadera para n=1

2. Hipótesis inductiva (n=h)

$\sum _{k=1}^h(2k-1)3^k=(h-1)3^{h+1}+3$

3. Tesis inductiva (n=h+1)

$\sum _{k=1}^{h+1}(2k-1)3^k=(h+1-1)3^{h+1+1}+3$

$\sum _{k=1}^{h+1}(2k-1)3^k=h{3}^{h+2}+3$

4. Demostración de la tesis con base a la hipótesis

$\sum _{k=1}^{h+1}(2k-1)3^k=\sum _{k=1}^h(2k-1)3^k+(2(h+1)-1)3^{h+1}$

Se aplica la hipótesis de inducción:

$\sum _{k=1}^{h+1}(2k-1)3^k=(h-1)3^{h+1}+3+[2(h+1)-1]3^{h+1}$

$\sum _{k=1}^{h+1}(2k-1)3^k=(h-1)3^{h+1}+3+(2h+2-1)3^{h+1}$

$\sum _{k=1}^{h+1}(2k-1)3^k=3^{h+1}(h-1+2h+1)+3$ (sacando factor común)

$\sum _{k=1}^{h+1}(2k-1)3^k=3^{h+1}3h+3$

$\sum _{k=1}^{h+1}(2k-1)3^k=h{3}^{h+2}+3$

Por lo tanto es correcto la afirmación, verificándose la proposición para $n=1$ y para $n=k+1$ siendo $k$ cualquier número natural, la proposición se verifica $\mathrm{\forall }n\in \mathbb{N}$.

Ejemplo 3

El teorema del binomio es el siguiente:

${(a+b)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k}){\left(a\right)}^k{\left(b\right)}^{n-k}$ donde $a,b\in ℝ$ y $n\in \mathbb{N}$

Asimilamos que el concepto de coeficiente binomial es el siguiente:

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}$

Para demostrar el teorema del binomio puede verificarse que para $n=1$ es verdadero

1. Se comprueba para $n=1$:

${(a+b)}^1=a+b$

$\sum _{k=0}^1(\genfrac{}{}{0ex}{}{1}{k}){\left(a\right)}^k{\left(b\right)}^{1-k}=a^0{b}^1+a^1{b}^0=a+b$

Por tanto, es cierto para $n=1$

Sabiendo que para $n=1$ el teorema se cumple se debe demostrar que es verdadero para $n+1$

2. Suponiendo cierto para $n$, se comprueba para $n+1$

$(a+b{)}^{n+1}=(a+b)(a+b{)}^n=(a+b)\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k}){\left(a\right)}^k{\left(b\right)}^{n-k}=$

$=a\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k}){\left(a\right)}^k{\left(b\right)}^{n-k}+b\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k}){\left(a\right)}^k{\left(b\right)}^{n-k}=$

$=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^{k+1}{b}^{n-k}+\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^k{b}^{(n+1)-k}=$

$=a^{n+1}+\sum _{k=1}^n(\genfrac{}{}{0ex}{}{n}{k-1})a^k{b}^{(n+1)-k}+\sum _{k=1}^n(\genfrac{}{}{0ex}{}{n}{k})a^k{b}^{(n+1)-k}+b^{n+1}=$

$=a^{n+1}+\sum _{k=1}^n[(\genfrac{}{}{0ex}{}{n}{k-1})+(\genfrac{}{}{0ex}{}{n}{k})]a^k{b}^{(n+1)-k}+b^{n+1}=$

$=a^{n+1}+b^{n+1}+\sum _{k=1}^n(\genfrac{}{}{0ex}{}{n+1}{k})a^k{b}^{(n+1)-k}=\sum _{k=0}^{n+1}(\genfrac{}{}{0ex}{}{n+1}{k})a^k{b}^{(n+1)-k}$

Como resultado obtenemos:

${(a+b)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k}){\left(a\right)}^k{\left(b\right)}^{n-k},\mathrm{\forall }n\in \mathbb{N}$

La demostración está basada en el axioma denominado principio de la inducción matemática. Plantilla:Cita

Ejemplo 4

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.

Paso 1. (Base de inducción)

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 $7=1*3+1*4$

Paso 2. (Base de inducción)

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

Hipótesis de inducción

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

Demostración

Si $n=3r+4s$, entonces, $(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:

• $3r+4s+1=3(r-1)+4(s+1)$ si $r>0$
• $3r+4s+1=3(r+3)+4(s-2)$ si $r=0$

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

Ejemplo 5

Propuesta: Demostrar que $n!>2^n$ para toda $n\ge 4$

Paso 1. (Base de inducción)

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

Paso 2. Hipótesis de inducción

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

Demostración

Como $n\ge 4\iff (n+1)\ge 5$ , por tanto, $2^n(n+1)\ge 2^n(5)>2^n(2)=2^{n+1}$.

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

Ejemplo 6

Se debe demostrar que $1\cdot 2\cdot 3\cdot 4\cdot \cdot \cdot n>2^n$

Paso 1. (Base de inducción)

Para n = 4, $1\cdot 2\cdot 3\cdot 4\cdot \cdot \cdot n>2^4\iff 24>16$

Paso 2. Hipótesis de inducción

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 $1\cdot 2\cdot 3\cdot 4\cdot \cdot \cdot n>2^n$ para $n\ge 4$

Demostración

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

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

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 solo para todos los números n mayores o iguales a un cierto número b, entonces la prueba por inducción consiste en:

1. Mostrando que la afirmación es válida cuando n = b.
2. Mostrando que si la afirmación es válida para algunos Plantilla:Nowrap entonces la misma declaración también es válida para Plantilla:Nowrap.

Esto puede usarse, por ejemplo, para mostrar que Plantilla:Nowrap para Plantilla:Nowrap.

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.

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 Plantilla:Nowrap bajo la suposición de que P(n) se cumple para cualquier número natural n menor que Plantilla:Nowrap; 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. 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 Plantilla:Nowrap". 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 Plantilla:Nowrap 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).

Ejemplo

Para este ejemplo se puede partir de lo siguiente:

Sea $\phi$ una proposición de los naturales tal que para todo m en los naturales y para todo $k$ menor que $m$ se cumple que $\phi (k)\Rightarrow \phi (m)$, entonces, para todo $n$ en los naturales, $\phi (n)$ es cierto.

Expresándolo de forma matemática:

$\mathrm{\forall }m\in \mathbb{N}$ ( [$\mathrm{\forall }k<m$ $\phi (k)$] $\Rightarrow \phi (m)$ ) $\Rightarrow \mathrm{\forall }n\in \mathbb{N}$ $\phi (n)$.

Empleando el principio del buen orden:

• Supongamos un conjunto A como el conjunto de todos los números naturales que no cumplen la proposición enunciada anteriormente => A = {$n\in \mathbb{N}|\mathrm{\neg }\phi (n)$} donde A no tiene mínimo => $A=\varnothing$.

• El objetivo es conseguir una contradicción partiendo de que A sí tiene mínimo, por tanto, m = min(A): $\mathrm{\forall }k<m(k\notin A)\wedge m\in A$.

• Por tanto, de forma contradictoria, k no está en el conjunto A: $\mathrm{\forall }k<m(k\notin [n\in \mathbb{N}\mid \mathrm{\neg }\phi (n)])$ lo que conlleva a que no se cumpla la proposición $\phi$ => $\mathrm{\forall }k<m[\mathrm{\neg }(\mathrm{\neg }\phi (k))]=\mathrm{\forall }k<m[\phi (k)]$.
• Debido a que es falso que no se cumpla $\phi (n)$ => $m\notin A$.

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

La propiedad del buen orden

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.

Ejemplo

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 0Plantilla:Esd$\le$ r $\le$ d y aPlantilla:Esd=Plantilla:EsddcPlantilla:Esd+Plantilla:Esdr.

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$\le$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$\le$r$\le$d.

Véase también

• Recurrencia
• Número natural
• Paradoja del caballo
• Axiomas de Peano

Enlaces externos

• Plantilla:MathWorld
• Plantilla:Planetmath
• Números naturales, principio de inducción
• Inducción Fuerte - Definición, Ejemplos y Ejercicios - Álgebra Superior 22
• AATA Principio de Inducción