6.2: Inducción básica

Supongamos que queremos mostrar que\(n!\) es al menos\(2^n − 2\), para cada\(n ≥ 1\) (donde\(n\) debe ser un entero). Podríamos comenzar a verificar este hecho para cada uno de los valores posibles para\(n\):

\[\begin{equation} \begin{split} 1!&= 1 ≥ 2^1 − 2 = 0; \\ 2!&= 2 ≥ 2^2 − 2 = 2; \\ 3!&= 6 ≥ 2^3 − 2 = 6; \\ 4!&= 24 ≥ 2^4 − 2 = 14. \end{split} \end{equation} \]

Podríamos seguir verificando los valores uno a la vez, pero el proceso continuaría para siempre, así que nunca podríamos completar la prueba.

En cambio, piensa en el siguiente método. Sabemos que la desigualdad aguanta\(n = 1\). Supongamos que la desigualdad tiene algún valor\(n = k\), es decir, que

\[k! ≥ 2^k − 2.\]

Ahora usemos el hecho de que podemos calcular fácilmente\((k+1)!\) a partir de\(k!\) junto con nuestra suposición, para deducir que la desigualdad sostiene cuándo\(n = k + 1\), es decir, que

\[(k + 1)! ≥ 2^{k+1} − 2.\]

Esto es suficiente para probar la desigualdad por cada entero\(n ≥ 1\) porque aplicar nuestra suposición y deducción suficientes tiempos demostrará la desigualdad por cualquier valor ¡en todo lo que nos interese! Por ejemplo, si quisiéramos estar seguros de que la desigualdad es válida\(n = 100\), podríamos tomar el hecho de que sabemos que sirve para\(1\), para deducir que se sostiene para\(2\), entonces el hecho de que se sostiene para nos\(2\) permite deducir que se sostiene para\(3\). Al repetir esto\(97\) más veces, eventualmente vemos que ya que es válido\(99\), podemos deducir que se sostiene para\(100\).

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

Dejar\(P(n)\) ser una aserción sobre el entero\(n\). Si sabemos que

1. La aserción\(P(n_0)\) es verdadera para algún entero particular\(n_0\); y
2. Para cualquier entero\(k ≥ n_0\), si\(P(k)\) es verdadero entonces también\(P(k + 1)\) debe ser verdadero, entonces\(P(n)\) es verdadero para cada entero\(n ≥ n_0\).

Definición: Hipótesis inductiva

En una prueba por inducción, determinar que\(P(n_0)\) es cierto para algún entero en particular\(n_0\) se llama el caso base. Demostrando la declaración condicional de que\(P(k) ⇒ P(k + 1)\) para cada uno\(k ≥ n_0\) se llama el paso inductivo. El supuesto que hacemos en el paso inductivo, que\(P(k)\) es cierto para algunos arbitrarios\(k ≥ n_0\), se denomina hipótesis inductiva, y puede ser referido por (IH) cuando se está utilizando en la prueba.

Ahora que hemos pasado por los trámites, escribamos una prueba adecuada por inducción de la desigualdad que usamos para introducir esta idea.

Ejemplo\(\PageIndex{1}\)

Demostrar por inducción que\(n! ≥ 2^n − 2\), por cada entero\(n ≥ 2\). (Esta desigualdad es en realidad cierta para todos\(n ≥ 0\), pero la prueba es considerablemente más simple si restringimos nuestra atención a\(n ≥ 2\)).

Solución

Caso base:\(n = 2\). Tenemos\(n! = 2! = 2\), y

\(2^n − 2 = 2^2 − 2 = 4 − 2 = 2.\)

Ciertamente\(2 ≥ 2\), por lo que la desigualdad aguanta\(n = 2\). Esto completa la prueba del caso base.

Paso inductivo: Comenzamos con la hipótesis inductiva. Seamos\(k ≥ 2\) arbitrarios, y supongamos que la desigualdad se sostiene\(n = k\); es decir, asuma eso\(k! ≥ 2^k − 2\).

Ahora queremos deducir que

\((k + 1)! ≥ 2^{k+1} − 2.\)

Empecemos por el lado izquierdo de esta desigualdad. Por la definición de factorial, sabemos que

\((k + 1)! = (k + 1)k!\)

Ahora que tenemos\(k!\) en la expresión, estamos en condiciones de aplicar la hipótesis inductiva; es decir,

\((k + 1)! = (k + 1)k! ≥ (k + 1)(2^k − 2).\)

Ya que\(k ≥ 2\), tenemos\(k + 1 ≥ 3\), así

\((k + 1)(2^k − 2) ≥ 3(2^k − 2) = 2(2^k ) + 2^k − 6 = 2^{k+1} + 2^k − 6.\)

Nuevamente\(k ≥ 2\), ya que, tenemos\(2k ≥ 4\), así\(2k − 6 ≥ −2\). De ahí

\((k + 1)! ≥ 2^{k+1} + 2^k − 6 ≥ 2^{k+1} − 2\)

que es lo que queríamos deducir. Esto completa la prueba del paso inductivo.

Por el Principio de Inducción Matemática,\(n! ≥ 2^n − 2\) por cada entero\(n ≥ 2\).

Las pruebas por inducción funcionan de manera muy natural con secuencias definidas recursiblemente, ya que la relación de recurrencia nos da información sobre el\((k + 1)^{\text{st}}\) término de la secuencia, con base en términos anteriores.

Ejemplo\(\PageIndex{2}\)

Considera la suma de los primeros\(n\) enteros. Podemos pensar en esto como una secuencia recursiblemente definida, definiendo\(s_1 = 1\), y\(s_n = s_{n−1} + n\), para cada\(n ≥ 2\). Así,\(s_2 = 1 + 2\);

\(s_3 = s_2 + 3 = 1 + 2 + 3\),

y así sucesivamente. Demostrar por inducción que\(s_n = \dfrac{n(n + 1)}{2}\), para cada\(n ≥ 1\).

Solución

Caso base:\(n = 1\). Tenemos\(s_n = s_1 = 1\), y

\(\dfrac{n(n + 1)}{2} = \dfrac{1(2)}{2} = 1\),

por lo que la igualdad se sostiene para\(n = 1\). Esto completa la prueba del caso base.

Paso inductivo: Comenzamos con la hipótesis inductiva. Seamos\(k ≥ 1\) arbitrarios, y supongamos que la igualdad se mantiene para\(n = k\); es decir, asuma eso\(s_k = \dfrac{k(k + 1)}{2}\).

Ahora queremos deducir que

\(s_{k+1} = \dfrac{(k + 1)(k + 2)}{2}\).

Usando la relación recursiva, tenemos\(s_{k+1} = s_k + (k+ 1)\) desde entonces\(k+ 1 ≥ 2\), y usando la hipótesis inductiva, tenemos\(s_k = \dfrac{k(k + 1)}{2}\), así que juntando estas, vemos que

\(s_{k+1} = \dfrac{k(k + 1)}{2} + (k + 1)\).

Sacar un factor común de\(k + 1\) da

\(s_{k+1} = (k + 1)(\dfrac{k}{2} + 1) = \dfrac{(k + 1)(k + 2)}{2}\),

que es lo que queríamos deducir. Esto completa la prueba del paso inductivo.

Por el Principio de Inducción Matemática,\(s_n = \dfrac{n(n + 1)}{2}\) para cada\(n ≥ 1\).

Nota

Los pasos de una prueba por inducción están definidos con precisión, y si dejas fuera alguno de ellos, u olvidas las condiciones requeridas, las cosas pueden salir mal. El caso base puede parecer obvio, pero no puede quedar fuera; también, la hipótesis que\(k ≥ n_0\) puede ser crítica para la prueba, como vimos en el Ejemplo 6.2.1.

Veamos un ejemplo donde, al olvidarnos de incluir el caso base, podemos dar una “prueba por inducción” de algo que es claramente falso.

Ejemplo\(\PageIndex{3}\)

Aquí hay una “prueba por inducción” (sin un caso base) de que cada entero\(n\) es al menos\(1000\).

Solución

Paso inductivo: Comenzamos con la hipótesis inductiva. Que\(k\) sea arbitrario, y supongamos que\(k ≥ 1000\).

Ahora queremos deducir eso\(k + 1 ≥ 1000\). Pero claramente,

\(k + 1 ≥ k ≥ 1000\)

(por nuestra hipótesis inductiva), que es lo que queríamos deducir. Esto completa la prueba del paso inductivo.

Por el Principio de Inducción Matemática,\(n ≥ 1000\) por cada entero\(n\).

Ahora es tu turno de probar algunos, ¡pero no dejes de lado ninguno de los pasos!

Ejercicio\(\PageIndex{1}\)

Utilice el Principio de Inducción Matemática para probar lo siguiente:

1) Para la secuencia recursiblemente definida dada por\(b_1 = 5\) y\(b_n = b_{n−1} + 4\) para todos\(n ≥ 2\), probar que para cada entero\(n ≥ 1\),\(b_n = 5 + 4(n − 1)\).

2) Para la secuencia recursiblemente definida dada por\(c_1 = 3\) y\(c_n = c_{n−1} + 3 · 2^{n−1}\) para todos\(n ≥ 2\), probar que para cada entero\(n ≥ 1\),\(c_n = 3(2^n − 1)\).

3) Demostrar que para cada entero\(n ≥ 0\),\(n! ≥ n\).

4) Demostrar que para cada entero\(n ≥ 0\),\(4^n − 1\) es divisible por\(3\).

5) Comenzando con\(n = 2\) y aumentando n a partir de ahí, calcule los primeros valores para el producto

\(t_n = \prod_{j=2}^{n} \left( 1 - \dfrac{1}{j} \right)\)

Conjetura una fórmula cerrada\(t_n\) basada en los valores que has calculado, y usa la inducción para demostrar que tu fórmula es correcta.

6) Demostrar que por cada entero\(n ≥ 1\),

\(\sum_{j=1}^{n} j! ≤ \dfrac{1}{2} (n + 1)!\)

7) Definir\(c_0 = 1\) y para\(n ≥ 1\), definir\(c_n = nc_{n−1} + 1\). Demostrar por inducción: para\(n ≥ 0\),

\(c_n = \sum_{j=0}^{n} \dfrac{n!}{(n-j)!}\)