Supongamos que queremos demostrar que
\begin{equation*} 1 + 2 + \cdots + n = \frac{n(n + 1)}{2} \end{equation*}para cualquier número natural \(n\text{.}\) Esta fórmula se puede verificar fácilmente para números pequeños tales como \(n = 1\text{,}\) 2, 3, o 4, pero es imposible de verificar para todos los número naturales uno por uno. 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 una fórmula para el caso \((n + 1)\) a partir de este conocimiento. La fórmula es verdadera para \(n = 1\) pues
\begin{equation*} 1 = \frac{1(1 + 1)}{2}. \end{equation*}Si hemos verificado los primeros \(n\) casos, entonces
\begin{align*} 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}. \end{align*}Esto corresponde exactamente a la fórmula para el caso \((n + 1)\text{.}\)
Este método de demostración se conoce como inducción matemática o simplemente inducción si no hay riesgo de confusión. En lugar de intentar verificar una proposición sobre un subconjunto \(S\) de los enteros positivos \({\mathbb N}\) uno por uno, una tarea imposible si \(S\) es un conjunto infinito, entregamos una demostración directa para el primer entero considerado, seguida de un argumento genérico mostrando que si la proposición se cumple en un cierto caso, entonces también se cumple para el siguiente caso en la sucesión. Resumimos la inducción matemática en el siguiente axioma.
Sea \(S(n)\) una proposición sobre números enteros para \(n \in {\mathbb N}\) y supongamos que \(S(n_0)\) es verdadera para algún entero \(n_0\text{.}\) Si para todos los enteros \(k\) con \(k \geq n_0\text{,}\) \(S(k)\) implica \(S(k+1)\text{,}\) es verdadera, entonces \(S(n)\) es verdadera para todos los enteros \(n\) mayores o iguales a \(n_0\text{.}\)
Para todos los enteros \(n \geq 3\text{,}\) \(2^n \gt n + 4\text{.}\) Como
\begin{equation*} 8 = 2^3 \gt 3 + 4 = 7, \end{equation*}la afirmación es verdadera para \(n_0 = 3\text{.}\) Supongamos que \(2^k \gt k + 4\) para \(k \geq 3\text{.}\) Entonces \(2^{k + 1} = 2 \cdot 2^{k} \gt 2(k + 4)\text{.}\) Pero
\begin{equation*} 2(k + 4) = 2k + 8 \gt k + 5 = (k + 1) + 4 \end{equation*}pues \(k\) es positivo. Luego, por inducción, la afirmación se cumple para todos los enteros \(n \geq 3\text{.}\)
El entero \(10^{n + 1} + 3 \cdot 10^n + 5\) es divisible por 9 para todo \(n \in {\mathbb N}\text{.}\) Para \(n = 1\text{,}\)
\begin{equation*} 10^{1 + 1} + 3 \cdot 10 + 5 = 135 = 9 \cdot 15 \end{equation*}es divisible por 9. Supongamos que \(10^{k + 1} + 3 \cdot 10^k + 5\) es divisible por 9 para \(k \geq 1\text{.}\) 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.
Demostraremos el teorema del binomio por inducción; es decir,
\begin{equation*} (a + b)^n = \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k}, \end{equation*}donde \(a\) and \(b\) son números reales, \(n \in \mathbb{N}\text{,}\) y
\begin{equation*} \binom{n}{k} = \frac{n!}{k! (n - k)!} \end{equation*}es el coeficiente binomial. Primero mostraremos que
\begin{equation*} \binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}. \end{equation*}Este resultado es consecuencia de
\begin{align*} \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}. \end{align*}Si \(n = 1\text{,}\) el teorema del binomio es fácil de verificar. Ahora supongamos que el resultado es verdadero para \(n\) mayor o igual a 1. 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}\right)\\ & = \sum_{k = 0}^{n} \binom{n}{k} a^{k + 1} b^{n - k} + \sum_{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} + \sum_{k = 1}^{n} \left[ \binom{n}{k - 1} + \binom{n}{k} \right]a^k b^{n + 1 - k} + b^{n + 1}\\ & = \sum_{k = 0}^{n + 1} \binom{n + 1}{k} a^k b^{n + 1- k}. \end{align*}Tenemos una proposición equivalente al Primer Principio de Inducción que en ocasiones será necesaria.
Sea \(S(n)\) una afirmación sobre enteros para \(n \in {\mathbb N}\) y supongamos que \(S(n_0)\) es verdadera para algún entero \(n_0\text{.}\) Si \(S(n_0), S(n_0 + 1), \ldots, S(k)\) implican \(S(k + 1)\) para \(k \geq n_0\text{,}\) entonces \(S(n)\) es verdadera para todos los enteros \(n \geq n_0\text{.}\)
Un subconjunto \(S\) de \({\mathbb Z}\) está bien-ordenado si todo subconjunto no vacío de \(S\) contiene un menor elemento. Note que el conjunto \({\mathbb Z}\) no está bien-ordenado pues no contiene un elemento mínimo. Los números naturales sin ambargo, sí están bien-ordenados.
El conjunto de los números naturales está bien-ordenado.
El Principio del Buen-Orden es equivalente al Principio de Inducción.
El principio de Inducción implica que \(1\) es el menor número natural positivo.
Sea \(S = \{ n \in {\mathbb N} : n \geq 1 \}\text{.}\) Entonces \(1 \in S\text{.}\) Supongamos que \(n \in S\text{.}\) Como \(0 \lt 1\text{,}\) se debe tener que \(n = n + 0 \lt n + 1\text{.}\) Por lo tanto, \(1 \leq n \lt n + 1\text{.}\) Así, si \(n \in S\text{,}\) entonces \(n + 1\) también debe estar en \(S\text{,}\) y por el Principio de Inducción, \(S = \mathbb N\text{.}\)
El Principio de Inducción implica el Principio del Buen-Orden. Es decir, todo subconjunto no vacío de \(\mathbb N\) contiene un menor elemento.
Debemos mostrar que si \(S\) es un subconjunto no vacío de los números naturales, entonces \(S\) contiene un elemento mínimo. Si \(S\) contiene a 1, el teorema es verdadero por el 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 mínimo. Si \(S\) no contiene un elemento menor a \(n+1\text{,}\) entonces \(n+1\) es el menor entero en \(S\text{.}\) De lo contrario, \(S\) debe contener un entero menor o igual a \(n\text{.}\) En ese caso, por la hipótesis de inducción, \(S\) contiene un elemento mínimo.
La Inducció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{.}\)
Mirar un problema de forma recursiva, en lugar de explícita, frecuentemente resulta en una mejor comprensión de situaciones complejas.
