1.3: Los números naturales y la inducción matemática

Asumiremos familiaridad con el conjunto\(\mathbb{N}\) de números naturales, con las operaciones aritméticas habituales de suma y multiplicación\(\mathbb{n}\), y con la noción de lo que significa que un número natural sea menor que otro.

Además, también asumiremos la siguiente propiedad de los números naturales.

Propiedad bien ordenado de los números naturales

Si\(A\) es un subconjunto no vacío de\(\mathbb{N}\), entonces existe un elemento\(\ell \in A\) tal que\(\ell \leq x\) para todos\(x \in A\).

Para parafrasear la propiedad anterior, cada subconjunto no vacío de enteros positivos tiene un elemento más pequeño.

El principio de inducción matemática es una herramienta útil para probar hechos sobre secuencias.

Teorema\(\PageIndex{1}\): Principle of Mathematical Induction

Para cada número natural\(n \in \mathbb{N}\), supongamos que eso\(P(n)\) denota una proposición que es verdadera o falsa. Vamos\(A=\{n \in \mathbb{N}: P(n) \text { is true }\}\). Supongamos que se mantienen las siguientes condiciones:

1. \(1 \in A\).
2. Para cada uno\(k \in \mathbb{N}\), si\(k \in A\), entonces\(k+1 \in A\).

Entonces\(A = \mathbb{N}\).

Prueba

Supongamos que las condiciones (a) y (b) se mantienen. Asumir, a modo de contradicción, eso\(A \neq \mathbb{N}\). Set\(B=\mathbb{N} \backslash A\), es decir\(B=\{n \in \mathbb{N}: P(n) \text { is false }\}\). Entonces\(B\) es un subconjunto no vacío de\(\mathbb{N}\). Por la Propiedad Bien Ordenada de los números naturales, existe un elemento más pequeño\(\ell \in B\) y, de ahí, tenemos que\(P(k)\) es cierto. Por condición (b), obtenemos que\(P(k+1)\) es cierto. Pero\(k+1= \ell\), y\(P(\ell)\) es falso, ya que\(\ell \in B\). Esto es una contradicción, por lo que sigue la conclusión. \(\square\)

Parafraseando, el principio dice que, dada una lista de proposiciones\(P(n)\), una para cada una\(n \in \mathbb{N}\), si\(P(1)\) es verdad y, además,\(P(k+1)\) es verdad siempre que\(P(k)\) es verdad, entonces todas las proposiciones son verdaderas.

Nos referiremos a este principio como inducción matemática o simplemente inducción. La condición (a) anterior se llama el caso base y la condición (b) el paso inductivo. Al probar (b), la declaración\(P(k)\) se denomina hipótesis inductiva.

Ejemplo\(\PageIndex{1}\)

Demostrar usando inducción que para todos\(n \in \mathbb{N}\)

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

Solución

El enunciado\(P(n)\) es la igualdad\(1+2+\cdots+n=\frac{n(n+1)}{2}\). Ahora el caso base dice eso\(1=\frac{1(1+1)}{2}\), lo cual es claramente cierto.

Supongamos que\(P(k)\) es cierto para algunos\(k \in \mathbb{N}\). Es decir, supongamos que\(1+2+\cdots+n=\frac{k(k+1)}{2}\) (esta es la hipótesis inductiva). Ahora tenemos

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

Esto demuestra que\(P(k+1)\) es cierto. Ahora hemos probado las condiciones (a) y (b) del Teorema 1.3.1. Por lo tanto, por el principio de inducción matemática concluimos que

\[1+2+\cdots+n=\frac{n(n+1)}{2} \text { for all } n \in \mathbb{N}.\]

Ejemplo\(\PageIndex{2}\)

Demostrar usando inducción que para todos\(n \in \mathbb{N}, 7^{n}-2^{n}\) es divisible por 5.

Solución

Porque\(n=1\), tenemos\(7-2=5\), que es claramente un múltiplo de 5.

Supongamos que\(7^{k}-2^{k}\) es un múltiplo de 5 para algunos\(k \in \mathbb{N}\). Es decir, hay un entero\(j\) tal que\(7^{k}-2^{k}=5 j\). Escribamos\(7^{k}-2^{k}=5 j\). Ahora bien, sustituyendo esta expresión a continuación, tenemos

\[7^{k+1}-2^{k+1}=7 \cdot 7^{k}-2 \cdot 2^{k}=7\left(2^{k}+5 j\right)-2 \cdot 2^{k}=7 \cdot 2^{k}-2 \cdot 2^{k}+7 \cdot 5 j=2^{k}(7-2)+5 \cdot 7 j=5\left(2^{k}+7 j\right)\]

De ello se deduce que\(7^{k+1}-2^{k+1}\) es un múltiplo de 5. Esto demuestra el paso inductivo.

Concluimos por inducción que\(7^{n}-2^{n}\) es divisible por 5 para todos\(n \in \mathbb(N)\).

Ejemplo\(\PageIndex{3}\)

Demostrar usando inducción que para todos\(n \in \mathbb{N}\)

\[n+1 \leq 2^{n}\]

Solución

Porque\(n=1\), tenemos\(1+1=2=2^{1}\), por lo que el caso base es cierto.

Supongamos que a continuación\(k+1 \leq 2^{k}\) para algunos\(k \in \mathbb{N}\). Entonces\(k+1+1 \leq 2^{k}+1\). Ya que\(2^{k}\) es un entero positivo, también tenemos\(1 \leq 2^{k}\). Por lo tanto,

\[(k+1)+1 \leq 2^{k}+1 \leq 2^{k}+2^{k}=2 \cdot 2^{k}=2^{k+1}.\]

Concluimos por el principio de inducción matemática que\(n+1 \leq 2^{n}\) para todos\(n \in \mathbb{N}\).

El siguiente resultado se conoce como el Principio Generalizado de Inducción Matemática. Simplemente establece que podemos iniciar el proceso de inducción en cualquier entero\(n_{0}\), y luego obtenemos la verdad de todas las declaraciones\(P(n)\) para\(n \geq n_{0}\).

Teorema\(\PageIndex{2}\) - Generalized Principle of Mathematical Induction.

Dejar\(n_{0} \in \mathbb{N}\) y para cada natural\(n \geq n_{0}\), supongamos que eso\(P(n)\) denota una proposición que sea verdadera o falsa. Vamos\(A=\{n \in \mathbb{N}: P(n) \text{ is true}\}\). Supongamos que se mantienen las siguientes dos condiciones:

1. \(n_{0} \in A\).
2. Para cada uno\(k \in \mathbb{N}\)\(k \geq n_{0}\),, si\(k \in A\), entonces\(k+1 \in A\).

Prueba

Supongamos que las condiciones (a) y (b) se mantienen. Asumir, a modo de contradicción, eso\(A \nsupseteq\{k \in \mathbb{N}: \left.k \geq n_{0}\right\}\). Set\(B=\left\{n \in \mathbb{N}: n \geq n_{0}, P(n) \text { is false }\right\}\). Entonces\(B\) es un subconjunto no vacío de\(\mathbb{N}\). Por la Propiedad Bien Ordenada de los números naturales, existe un elemento más pequeño\(\ell \in B\). Por condición (a),\(n_{0} \notin B\). De ahí,\(\ell \geq n_{0}+1\). De ello se deduce que\(k=\ell-1 \geq n_{0}\). Ya que\(k<\ell\),\(k \notin B\) y, entonces, tenemos eso\(P(k)\) es cierto. Por condición (b), obtenemos que\(P(k+1)\) es cierto. Pero\(k+1= \ell\), y\(P(\ell)\) es falso, ya que\(\ell \in B\). Esto es una contradicción, por lo que sigue la conclusión. \(\square\)

Ejemplo\(\PageIndex{4}\)

Demostrar por inducción que\(3 n<2^{\prime}\) para todos\(n \geq 4\).

Solución

El enunciado es cierto\(n=4\) desde entonces\(12<16\). Supongamos a continuación que\(3 k<2^{k}\) para algunos\(k \in \mathbb{N}\),\(k \geq 4\). Ahora,

\[3(k+1)=3 k+3<2^{k}+3<2^{k}+2^{k}=2^{k+1},\]

donde la segunda desigualdad sigue desde entonces\(k \geq 4\) y, así,\(2^{k} \geq 16>3\). Esto demuestra que\(P(k+1)\) es cierto. Así, por el principio generalizado de inducción, la desigualdad se mantiene para todos\(n \geq 4\).

A continuación presentamos otra variante del principio de inducción que facilita la prueba del paso inductivo. A pesar de su nombre, este principio es equivalente al estándar.

Teorema\(\PageIndex{3}\) - Principle of Strong Induction.

Para cada natural\(n \in \mathbb{N}\), supongamos que\(P(n)\) denota una proposición que sea verdadera o falsa. Vamos\(A=\{n \in \mathbb{N}: P(n) \text { is true }\}\). Supongamos que se mantienen las siguientes dos condiciones:

1. \(1 \in A\).
2. Para cada uno\(k \in \mathbb{N}\), si\(1,2, \ldots, k \in A\), entonces\(k+1 \in A\)

Entonces\(A = \mathbb{N}\).

Prueba

Agrega prueba aquí y automáticamente se ocultará

OBSERVACIÓN\(\PageIndex{4}\)

Obsérvese que el paso inductivo anterior dice que, para probar que\(P(k+1)\) es cierto, podemos suponer no sólo que eso\(P(k)\) es cierto, sino que también eso\(P(1), P(2), \ldots, P(k-1)\) es cierto.

También hay una versión generalizada de este teorema donde el caso base es para algún entero\(n_{0}>1\).

Ejemplo\(\PageIndex{5}\)

Demostrar por inducción que cada entero positivo mayor que 1 es un número primo o un producto de números primos.

Solución

Claramente, la afirmación es cierta para\(n=2\). Supongamos que la sentencia se mantiene para cualquier entero positivo\(m \in\{2, \ldots, k\}\), donde\(k \in \mathbb{N}\),\(k \geq 2\). Si\(k+1\) es primo, la declaración se mantiene para\(k+1\). De lo contrario, hay enteros positivos\(p, q>1\) tales que\(k+1=pq\). Ya que\(p, q \leq k\), por la suposición inductiva aplicada a ambos\(p\) y\(q\) podemos encontrar números primos\(r_{1}, \ldots, r_{\ell}\) y\(s_{1}, \ldots, s_{m}\) tales que\(p=r_{1} \cdots r_{\ell}\) y\(q=s_{1} \cdots s_{m}\) (tenga en cuenta que\(\ell\) y\(m\) pueden ser ambos iguales a 1). Pero entonces

\[k+1=r_{1} \cdots r_{\ell} s_{1} \cdots s_{m}\]

Así, la afirmación se mantiene cierta para\(k+1\). La conclusión sigue ahora por el principio de Inducción Fuerte.

Ejercicio\(\PageIndex{1}\)

Demostrar lo siguiente usando Inducción Matemática.

1. \(1^{2}+2^{2}+\cdots+n^{2}=\frac{n(n+1)(2 n+1)}{6} \text { for all } n \in \mathbb{N}\).
2. \(1^{3}+2^{3}+\cdots+n^{3}=\frac{n^{2}(n+1)^{2}}{4} \text { for all } n \in \mathbb{N}\).
3. \(1+3+\cdots+(2 n-1)=n^{2} \text { for all } n \in \mathbb{N}\).

Responder

Agrega textos aquí. No borre primero este texto.

Ejercicio\(\PageIndex{2}\)

Demostrar que para todos\(n \in \mathbb{N}\),\(9^{n}-5^{n}\) es divisible por\(4\).

Responder

Agrega textos aquí. No borre primero este texto.

Ejercicio\(\PageIndex{3}\)

Demostrar que para todos\(n \in \mathbb{N}\),\(7^{n}-1\) es divisible por\(3\)

Responder

Agrega textos aquí. No borre primero este texto.

Ejemplo\(\PageIndex{4}\)

Demostrar lo siguiente mediante inducción.

1. \(2 n+1 \leq 2^{n}\)para\(n \geq 3\) (\(n \in \mathbb{N}\)).
2. \(n^{2} \leq 3^{n}\)para todos\(n \in \mathbb{N}\). (Pista: mostrar primero que para todos\(n \in \mathbb{N}\),\(2 n \leq n^{2}+1\). Esto no requiere inducción..)
3. \(n^{3} \leq 3^{n}\)para todos\(n \in \mathbb{N}\). (Pista: Verifique los casos\(n=1\) y\(n=2\) directamente y luego use la inducción para\(n \geq 3\).)

Solución

Agrega texto aquí.

Ejercicio\(\PageIndex{5}\)

Dado un número real\(a \neq 1\), demuestre que

\[1+a+a^{2}+\cdots+a^{n}=\frac{1-a^{n+1}}{1-a} \text { for all } n \in \mathbb{N}.\]

Responder

Agrega textos aquí. No borre primero este texto.

Ejercicio\(\PageIndex{6}\)

La secuencia de Fibonacci se define por

\[a_{1}=a_{2}=1 \text { and } a_{n+2}=a_{n+1}+a_{n} \text { for } n \geq 1.\]

Demostrar

\[a_{n}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right].\]

Responder

Agrega textos aquí. No borre primero este texto.

Ejercicio\(\PageIndex{7}\)

Vamos\(a \geq-1\). Demostrar por inducción que

\[(1+a)^{n} \geq 1+n a \text { for all } n \in \mathbb{N}.\]

Responder

Agrega textos aquí. No borre primero este texto.

Ejercicio\(\PageIndex{8}\)

Dejar\(a, b \in \mathbb{R}\) y\(n \in \mathbb{N}\). Utilizar la Inducción Matemática para probar el teorema binomial

\ [(a+b) ^ {n} =\ suma_ {k=0} ^ {n}\ izquierda (\ begin {array} {l}
n\\
k
\ end {array}\ derecha) a^ {k} b^ {n-k},\]

donde\ (\ left (\ begin {array} {l}
n\\
k
\ end {array}\ right) =\ frac {n!} {k! (n-k)!} \).

Responder

Agrega textos aquí. No borre primero este texto.