1.2: El principio de ordenación de pozos y la inducción matemática
- Page ID
- 115069
En esta sección, presentamos tres herramientas básicas que a menudo se utilizarán para probar las propiedades de los enteros. Comenzamos con una propiedad muy importante de enteros llamada principio de ordenamiento de pozos. Luego declaramos lo que se conoce como el principio del encasillamiento, y luego se procede a presentar un importante método llamado inducción matemática.
Definición: El principio de ordenamiento de pozos
Un elemento mínimo existe en cualquier conjunto no vacío de enteros positivos.
Este principio puede tomarse como un axioma sobre los enteros y será la clave para probar muchos teoremas. Como resultado, vemos que cualquier conjunto de enteros positivos está bien ordenado mientras que el conjunto de todos los enteros no está bien ordenado.
Definición: El principio del encasillamiento
Si\(s\) los objetos se colocan en\(k\) cajas para\(s>k\), entonces al menos una caja contiene más de un objeto.
Supongamos que ninguna de las cajas contiene más de un objeto. Después hay como máximo los\(k\) objetos. Esto lleva a una contradicción con el hecho de que hay\(s\) objetos para\(s>k\).
El principio de la inducción matemática
Presentamos ahora una valiosa herramienta para probar resultados sobre números enteros. Esta herramienta es el principio de inducción matemática.
El Primer Principio de Inducción Matemática: Si un conjunto de enteros positivos tiene la propiedad que, si contiene el entero\(k\), entonces también contiene\(k+1\), y si este conjunto contiene 1 entonces debe ser el conjunto de todos los enteros positivos. De manera más general, una propiedad relativa a los enteros positivos que es verdadera para\(n=1\), y que es verdadera para el entero\(n+1\) siempre que sea verdadera para el entero\(n\), debe ser verdadera para todos los enteros positivos.
Utilizamos el principio de ordenamiento de pozos para probar el primer principio de inducción matemática
Let\(S\) Ser el conjunto de enteros positivos que contiene el entero 1, y el entero\(k+1\) cada vez que contiene\(k\). Supongamos también que no\(S\) es el conjunto de todos los enteros positivos. Como resultado, hay algunos enteros que no están contenidos en\(S\) y por lo tanto esos enteros deben tener un elemento mínimo\(\alpha\) por el principio de ordenamiento del pozo. Observe que\(\alpha \neq 1\) desde\(1\in S\). Pero\(\alpha-1 \in S\) y así utilizando la propiedad de\(S\),\(\alpha \in S\). Por lo tanto,\(S\) deben contener todos los enteros positivos.
Presentamos ahora algunos ejemplos en los que utilizamos el principio de inducción.
Ejemplo\(\PageIndex{1}\)
Usa la inducción matemática para demostrar que\(\forall n\in \mathbb{N}\)\[\sum_{j=1}^nj=\frac{n(n+1)}{2}. \nonumber\]
Solución
Primero tenga en cuenta que
\[\sum_{j=1}^1j=1=\frac{1\cdot 2}{2} \nonumber\]
y así la afirmación es cierta para\(n=1\). Para el paso inductivo restante, supongamos que la fórmula se mantiene para\(n\), es decir\(\sum_{j=1}^nj=\frac{n(n+1)}{2}\). Demostramos que
\[\sum_{j=1}^{n+1}j=\frac{(n+1)(n+2)}{2}. \nonumber\]
para completar la prueba por inducción. Efectivamente\[\sum_{j=1}^{n+1}j=\sum_{j=1}^nj+(n+1)=\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2}, \nonumber\] y el resultado sigue.
Ejemplo\(\PageIndex{2}\)
Utilice la inducción matemática para demostrarlo\(n!\leq n^n\) para todos los enteros positivos\(n\).
Solución
Tenga en cuenta que\(1!=1\leq 1^1=1\). Presentamos ahora el paso inductivo. Supongamos que\[n!\leq n^n \nonumber\] para algunos\(n\), eso lo demostramos\((n+1)!\leq (n+1)^{n+1}\). Tenga en cuenta que
\[(n+1)!=(n+1)n!\leq (n+1).n^n<(n+1)(n+1)^{n}=(n+1)^{n+1}. \nonumber\]
Esto completa la prueba.
El Segundo Principio de Inducción Matemática: Un conjunto de enteros positivos que tiene la propiedad de que para cada entero\(k\), si contiene todos los enteros del 1 al\(k\) entonces contiene\(k+1\) y si contiene 1 entonces debe ser el conjunto de todos los enteros positivos. De manera más general, una propiedad relativa a los enteros positivos que es verdadera para\(n=1\), y que es cierta para todos los enteros hasta\(n+1\) cuando sea cierta para todos los enteros hasta\(n\), debe ser cierta para todos los enteros positivos.
El segundo principio de inducción también se conoce como el principio de inducción fuerte. Además, el primer principio de inducción se conoce como el principio de inducción débil.
Para probar el segundo principio de inducción, utilizamos el primer principio de inducción.
Let\(T\) Ser un conjunto de enteros conteniendo 1 y tal que por cada entero positivo\(k\), si contiene\(1,2,...,k\), entonces contiene\(k+1\). \(S\)Sea el conjunto de todos los enteros positivos\(k\) tal que todos los enteros positivos menores o iguales a\(k\) estén en\(T\). Entonces 1 está adentro\(S\), y también vemos que\(k+1\) está adentro\(S\). Así\(S\) debe ser el conjunto de todos los enteros positivos. Así\(T\) debe ser el conjunto de todos los enteros positivos ya que\(S\) es un subconjunto de\(T\).
Ejercicios
- Demostrar usando inducción matemática que\(n<3^n\) para todos los enteros positivos\(n\).
- \(\sum_{j=1}^nj^2=\frac{n(n+1)(2n+1)}{6}\)Demuéstralo.
- Usa la inducción matemática para demostrarlo\(\sum_{j=1}^n(-1)^{j-1}j^2=(-1)^{n-1}n(n+1)/2\).
- Usa la inducción matemática para demostrarlo\(\sum_{j=1}^nj^3=[n(n+1)/2]^2\) por cada entero positivo\(n\).
- Usa la inducción matemática para demostrar que\(\sum_{j=1}^n(2j-1)=n^2\)
- Utilice la inducción matemática para demostrar que\(2^n<n!\) para\(n\geq 4\).
- Utilice la inducción matemática para demostrar que\(n^2<n!\) para\(n\geq 4\).