4.2: Más sobre Inducción

En el apartado anterior, discutimos declaraciones probatorias de la forma\((\forall n \in \mathbb{N}) P(n)\). La inducción matemática puede ser utilizada para demostrar una familia más amplia de resultados; es decir, los de la forma

\((\forall n \in \mathbb{Z})(n \geq a \implies P(n))\)

por cualquier valor\(a \in \mathbb{Z}\). Teorema 4.2 maneja el caso especial cuando\(a = 1\). La analogía de escalera de la sección anterior se sostiene para esta situación más general, también. Para probar el siguiente teorema, imitar la prueba del Teorema 4.2, pero esta vez utilizar el conjunto\(S=\{k\in \mathbb{N}\mid P(a+k-1) \text{ is true}\}\).

Teorema 4.9. Let\(P(a), P(a+1), P(a+2), \ldots\) Ser una secuencia de sentencias, una por cada entero mayor o igual a\(a\). Supongamos que

1. \(P(a)\)es verdad, y
2. si\(P(k)\) es verdad, entonces\(P(k+1)\) es verdad.

Entonces\(P(n)\) es cierto para todos los enteros\(n \geq a\).

El teorema 4.9 da un proceso para probar declaraciones de la forma: “Para todos los enteros\(n\geq a\),”\(P(n)\). Como antes, la hipótesis (i) se llama el paso base, y (ii) se llama el paso inductivo.

Prueba de Esqueleto 4.10. Aquí está la estructura general para una prueba por inducción cuando el caso base no necesariamente implica\(a=1\).

Se procede por inducción.

1. Paso base: [Verifica que\(P(a)\) sea cierto. Esto a menudo, pero no siempre, equivale a\(n=a\) enchufarse en dos lados de alguna ecuación reclamada y que ambos lados son realmente iguales.]
2. Paso inductivo: [Tu objetivo es demostrar “Para todos\(k\in\mathbb{Z}\), si\(P(k)\) es verdad, entonces \(P(k+1)\)es verdad”.] Dejemos\(k \ge a\) ser un entero y supongamos que eso\(P(k)\) es cierto. [Hacer algo para derivar que \(P(k+1)\)sea cierto.] Por lo tanto,\(P(k+1)\) es cierto.

Así, por inducción,\(P(n)\) es cierto para todos los enteros\(n \ge a\).

Nos encontramos con el siguiente teorema de nuevo en la Sección 3.3 (ver Conjetura 3.29), pero no lo probamos. Al probar este teorema usando inducción, necesitarás argumentar que si agregas un elemento más a un conjunto finito, entonces terminas con el doble de subconjuntos. Para su caso base, considere el juego vacío.

Teorema 4.11. Si\(A\) es un conjunto finito con\(n\) elementos, entonces\(\mathcal{P}(A)\) es un conjunto con\(2^{n}\) elementos.

Teorema 4.12. Para todos los enteros\(n \ge 0\),\(n<2^n\).

Una consecuencia de los dos teoremas anteriores es que el conjunto de potencias de un conjunto finito siempre consiste en más elementos que el conjunto original.

Teorema 4.13. Para todos los enteros\(n \ge 0\),\(4\) divide\(9^n - 5\).

Teorema 4.14. Para todos los enteros\(n \ge 0\),\(4\) divide\(6\cdot 7^n - 2 \cdot 3^n\).

Teorema 4.15. Para todos los enteros\(n \ge 2\),\(2^n > n + 1\).

Teorema 4.16. Para todos los enteros\(n \ge 0\),\(1 + 2^1 + 2^2 + \cdots + 2^n = 2^{n+1} - 1\).

Teorema 4.17. Arreglar un número real\(r \neq 1\). Para todos los enteros\(n \ge 0\),\[\displaystyle{1 + r^1 + r^2 + \cdots + r^n = \frac{r^{n+1} - 1}{r-1}}.\]

Teorema 4.18. Para todos los enteros\(n \ge 3\),\(\displaystyle{2\cdot 3 + 3 \cdot 4 + \cdots + (n-1)\cdot n = \frac{(n-2)(n^2+2n+3)}{3}}\).

Teorema 4.19. Para todos los enteros\(n \ge 1\),\(\displaystyle{\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \cdots + \frac{1}{n(n+1)} = \frac{n}{n+1}}\).

Teorema 4.20. Para todos los enteros\(n \ge 1\),\(\displaystyle{\frac{1}{1\cdot 3} + \frac{1}{3\cdot 5} + \frac{1}{5\cdot7} + \cdots + \frac{1}{(2n-1)(2n+1)} = \frac{n}{2n+1}}\).

Teorema 4.21. Para todos los enteros\(n \ge 0\),\(3^{2n}-1\) es divisible por\(8\).

Teorema 4.22. Para todos los enteros\(n \ge 2\),\(2^n < (n+1)!\).

Teorema 4.23. Para todos los enteros\(n \ge 2\),\(2\cdot 9^n - 10 \cdot 3^n\) es divisible por\(4\).

Consideramos ahora un problema de inducción de otro tipo, donde hay que comenzar con alguna experimentación. Para la Parte (c), considere usar los resultados de las Partes (a) y (b).

Problema 4.24. Supongamos que\(n\) las líneas se dibujan en el plano de manera que no hay dos líneas paralelas y no se cruzan tres líneas en ningún punto. Tal colección de líneas se dice que está en posición general. Cada colección de líneas en posición general divide el plano en regiones disjuntas, algunas de las cuales son polígonos con área finita (regiones delimitadas) y algunas de las cuales no lo son (regiones no delimitadas).

1. \(R(n)\)Sea el número de regiones en las que se divide el plano por\(n\) líneas en posición general. Conjetura una fórmula para\(R(n)\) y demuestra que tu conjetura es correcta.
2. \(U(n)\)Sea el número de regiones no delimitadas en las que se divide el plano por\(n\) líneas en posición general. Conjetura una fórmula para\(U(n)\) y demuestra que tu conjetura es correcta.
3. \(B(n)\)Sea el número de regiones delimitadas en las que se divide el plano por\(n\) líneas en posición general. Conjetura una fórmula para\(B(n)\) y demuestra que tu conjetura es correcta.
4. Supongamos que coloreamos cada una de las regiones (delimitadas y no delimitadas) para que no haya dos regiones adyacentes (es decir, que compartan un borde común) que tengan el mismo color. ¿Cuál es el menor número de colores que podríamos usar para lograr esto? Demuestra tu aseveración.