2.1: Inducción matemática
- Page ID
- 111183
Supongamos que deseamos demostrar que
\[ 1 + 2 + \cdots + n = \frac{n(n + 1)}{2} \nonumber \]
para cualquier número natural\(n\text{.}\) Esta fórmula se verifica fácilmente para números pequeños como\(n = 1\text{,}\)\(2\text{,}\)\(3\text{,}\) o\(4\text{,}\) pero es imposible verificar para todos los números naturales caso por caso. Para demostrar que la fórmula es verdadera en general, se requiere un método más genérico.
Supongamos que hemos verificado la ecuación para los primeros\(n\) casos. Intentaremos demostrar que podemos generar la fórmula para el caso\((n + 1)\) th a partir de este conocimiento. La fórmula es cierta para\(n = 1\) ya
\[ 1 = \frac{1(1 + 1)}{2}\text{.} \nonumber \]
Si hemos verificado los primeros\(n\) casos, entonces
\ begin {alinear*} 1 + 2 +\ cdots + n + (n + 1) & =\ frac {n (n + 1)} {2} + n + 1\\ & =\ frac {n^2 + 3n + 2} {2}\\ & =\ frac {(n + 1) [(n + 1) + 1]} {2}\ texto {.} \ end {alinear*}
Esta es exactamente la fórmula para el caso\((n + 1)\) th.
Este método de prueba se conoce como inducción matemática. En lugar de intentar verificar una declaración sobre algún subconjunto\(S\) de los enteros\({\mathbb N}\) positivos caso por caso, una tarea imposible si\(S\) es un conjunto infinito, damos una prueba específica para el entero más pequeño que se está considerando, seguido de un argumento genérico que muestra que si el sentencia sostiene para un caso dado, entonces también debe sostenerse para el siguiente caso en la secuencia. Resumimos la inducción matemática en el siguiente axioma.
Dejar\(S(n)\) ser una declaración sobre enteros para\(n \in {\mathbb N}\) y supongamos que\(S(n_0)\) es cierto para algún entero\(n_0\text{.}\) Si para todos los enteros\(k\) con\(k \geq n_0\text{,}\)\(S(k)\) implica que\(S(k+1)\) es verdadero, entonces\(S(n)\) es cierto para todos los enteros\(n\) mayores que o iguales a\(n_0\text{.}\)
Para todos los enteros\(n \geq 3\text{,}\)\(2^n \gt n + 4\text{.}\) Desde
\[ 8 = 2^3 \gt 3 + 4 = 7\text{,} \nonumber \]
la afirmación es verdadera para\(n_0 = 3\text{.}\) Supongamos que\(2^k \gt k + 4\) para\(k \geq 3\text{.}\)
Solución
Entonces\(2^{k + 1} = 2 \cdot 2^{k} \gt 2(k + 4)\text{.}\) Pero
\[ 2(k + 4) = 2k + 8 \gt k + 5 = (k + 1) + 4 \nonumber \]
ya que\(k\) es positivo. Por lo tanto, por inducción, la sentencia se mantiene para todos los enteros\(n \geq 3\text{.}\)
Cada entero\(10^{n + 1} + 3 \cdot 10^n + 5\) es divisible por\(9\) para\(n \in {\mathbb N}\text{.}\) For\(n = 1\text{,}\)
\[ 10^{1 + 1} + 3 \cdot 10 + 5 = 135 = 9 \cdot 15 \nonumber \]
es divisible por\(9\text{.}\) Supongamos que\(10^{k + 1} + 3 \cdot 10^k + 5\) es divisible por\(9\) para\(k \geq 1\text{.}\)
Solución
Entonces
\ begin {align*} 10^ {(k + 1) + 1} + 3\ cdot 10^ {k + 1} + 5& = 10^ {k + 2} + 3\ cdot 10^ {k + 1} + 50 - 45\\ & = 10 (10^ {k + 1} + 3\ cdot 10^ {k} + 5) - 45\ end {align*}
es divisible por\(9\text{.}\)
Demostraremos el teorema binomial mediante inducción matemática; es decir,
\[ (a + b)^n = \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k}\text{,} \nonumber \]
dónde\(a\) y\(b\) son números reales,\(n \in \mathbb{N}\text{,}\) y
\[ \binom{n}{k} = \frac{n!}{k! (n - k)!} \nonumber \]
es el coeficiente binomial.
Solución
Primero demostramos que
\[ \binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}\text{.} \nonumber \]
Este resultado se desprende de
\ begin {alinear*}\ binom {n} {k} +\ binom {n} {k - 1} & =\ frac {n!} {k! (n - k)!} +\ frac {n!} {(k-1)! (n - k + 1)!} \\ & =\ frac {(n + 1)!} {k! (n + 1 - k)!} \\ & =\ binom {n + 1} {k}\ texto {.} \ end {alinear*}
Si\(n = 1\text{,}\) el teorema binomial es fácil de verificar. Ahora supongamos que el resultado es cierto para\(n\) mayor o igual a\(1\text{.}\) Entonces
\ begin {align*} (a + b) ^ {n + 1} & = (a + b) (a + b) ^n\\ & = (a + b)\ left (\ sum_ {k = 0} ^ {n}\ binom {n} {k} a^k b^ {n - k}\ derecha)\\ & =\ sum_ {k = 0} ^ {n}\ binom {n} {k} a^ {k + 1} b^ {n - k} +\ suma_ {k = 0} ^ {n}\ binom {n} {k} a^k b^ {n + 1 - k}\\ & = a^ {n + 1} +\ sum_ {k = 1} ^ {n}\ binom {n} {k - 1} a^ {k} b^ {n + 1 - k} +\ sum_ {k = 1} ^ {n}\ binom {n} {k} a^k b^ {n + 1 - k} + b^ {n + 1}\\ & = a^ {n + 1} +\ suma_ {k = 1} ^ {n}\ izquierda [\ binom {n} {k - 1} +\ binom {n} {k} derecha] a^k b^ {n + 1 - k} + b^ {n + 1}\\ & =\ sum_ {k = 0} ^ {n + 1}\ binom {n + 1} {k} a^k b^ {n + 1- k}\ text {.} \ end {alinear*}
Tenemos una declaración equivalente del Principio de Inducción Matemática que muchas veces es muy útil.
Dejar\(S(n)\) ser una declaración sobre enteros para\(n \in {\mathbb N}\) y supongamos que\(S(n_0)\) es cierto para algún entero\(n_0\text{.}\) Si\(S(n_0), S(n_0 + 1), \ldots, S(k)\) implica que\(S(k + 1)\) para\(k \geq n_0\text{,}\) entonces la declaración \(S(n)\)es cierto para todos los enteros\(n \geq n_0\text{.}\)
Un subconjunto no vacío\(S\) de\({\mathbb Z}\) está bien ordenado si\(S\) contiene un elemento mínimo. Observe que el conjunto no\({\mathbb Z}\) está bien ordenado ya que no contiene un elemento más pequeño. Sin embargo, los números naturales están bien ordenados.
Cada subconjunto no vacío de los números naturales está bien ordenado.
El Principio de Ordenación del Bien es equivalente al Principio de Inducción Matemática.
El Principio de Inducción Matemática implica que\(1\) es el número natural menos positivo.
- Prueba
-
Vamos\(S = \{ n \in {\mathbb N} : n \geq 1 \}\text{.}\) Entonces\(1 \in S\text{.}\) Supongamos que\(n \in S\text{.}\)\(0 \lt 1\text{,}\) Ya que debe darse el caso que\(n = n + 0 \lt n + 1\text{.}\) Por lo tanto, en\(1 \leq n \lt n + 1\text{.}\) consecuencia, si\(n \in S\text{,}\) entonces también\(n + 1\) debe estar en\(S\text{,}\) y por el Principio de Inducción Matemática, y tenemos\(S = \mathbb N\text{.}\)
El Principio de Inducción Matemática implica el Principio de Ordenamiento Bien. Es decir, cada subconjunto no vacío de\(\mathbb N\) contiene un elemento mínimo.
- Prueba
-
Debemos demostrar que si\(S\) es un subconjunto no vacío de los números naturales, entonces\(S\) contiene un elemento mínimo. Si\(S\) contiene 1, entonces el teorema es cierto por Lema 2.7. Supongamos que si\(S\) contiene un entero\(k\) tal que\(1 \leq k \leq n\text{,}\) entonces\(S\) contiene un elemento mínimo. Mostraremos que si un conjunto\(S\) contiene un entero menor o igual a\(n + 1\text{,}\) entonces\(S\) tiene un elemento menor. Si\(S\) no contiene un entero menor que\(n+1\text{,}\) entonces\(n+1\) es el entero más pequeño en\(S\text{.}\) De lo contrario, ya que no\(S\) está vacío,\(S\) debe contener un número entero menor o igual a\(n\text{.}\) En este caso, por inducción,\(S\) contiene un elemento mínimo.
La inducción también puede ser muy útil en la formulación de definiciones. Por ejemplo, hay dos formas de definir\(n!\text{,}\) el factorial de un entero positivo\(n\text{.}\)
- La definición explícita:\(n! = 1 \cdot 2 \cdot 3 \cdots (n - 1) \cdot n\text{.}\)
- La definición inductiva o recursiva:\(1! = 1\) y\(n! = n(n - 1)!\) para\(n \gt 1\text{.}\)
Todo buen matemático o informático sabe que mirar los problemas recursivamente, a diferencia de explícitamente, a menudo resulta en una mejor comprensión de cuestiones complejas.