6.3: Inducción más avanzada

Ahora que hemos revisado la forma básica de inducción, es importante considerar algunas formas más avanzadas que a menudo se utilizan. La primera forma que veremos es una fuerte inducción. Cuando tenemos una secuencia definida recursivamente que depende de los términos anteriores, a veces necesitamos saber no solo sobre el término único que viene inmediatamente antes del\(n^{\text{th}}\) término, sino sobre otros términos anteriores. Sólo juntando toda esta información podremos deducir el resultado que necesitamos sobre el\(n^{\text{th}}\) término.

Ejemplo\(\PageIndex{1}\)

Vamos a definir una secuencia recursivamente definida por\(a_1 = 2\) y para cada entero\(n ≥ 2\), tenemos

\(a_n = \sum_{i=1}^{n-1} a_i\).

Por lo tanto,\(a_2 = a_1 = 2\);

\(\begin{equation} \begin{split} a_3&= a_1 + a_2 = 2 + 2 = 4; \\ a_4&= a_1 + a_2 + a_3 = 2 + 2 + 4 = 8, \end{split} \end{equation} \)

y así sucesivamente. Demostrar por inducción que para cada\(n ≥ 2\), tenemos\(a_n = 2^{n−1}\).

Solución

Comenzamos con el caso base: cuando\(n = 2\), tenemos\(a_2 = 2 = 2^{2−1}\), entonces la igualdad es cierta para el caso base. Ahora para la hipótesis inductiva, dejamos\(k ≥ 2\) ser arbitrarios, y supongamos que la igualdad es verdad para\(n = k\), entonces\(a_k = 2^{k−1}\). Ahora\(n = k + 1\), cuando, tenemos

\(a_n = a_{k+1} = \sum_{i=1}^{k} a_i\),

por la relación recursiva para esta secuencia. Sabemos lo que\(a_1\) es, por nuestra condición inicial; eso lo sabemos\(a_k = 2^{k−1}\), pero ¿qué pasa con los valores intermedios? El Principio de Inducción Matemática tal y como lo hemos aprendido hasta ahora, no nos permite asumir nada sobre (por ejemplo)\(a_{k−1}\).

En realidad, sin embargo, la forma en que funciona el concepto de inducción, para cuando estamos tratando de probar algo sobre un, en realidad ya lo hemos deducido por cada valor entre\(n_0\) y\(n − 1\) (inclusive). Entonces no hay nada de malo en asumir que eso\(P(i)\) es cierto para cada valor entre\(n_0\) y\(k\), en lugar de solo para\(k\), para deducir que eso\(P(k + 1)\) es cierto. Más concretamente, esto es decir lo siguiente. Supongamos que al saber\(P(0)\) podemos deducir\(P(1)\), y luego por saber\(P(0)\) y\(P(1)\) podemos deducir\(P(2)\), y así sucesivamente, para que eventualmente al saber que todo desde el\(P(0)\) principio\(P(k)\) es cierto, podamos deducir que eso\(P(k + 1)\) es cierto.

Entonces\(P(n)\) es cierto para cada entero\(n ≥ 0\). Por supuesto, no tenemos por qué empezar\(0\); podemos comenzar con cualquier entero\(n_0\). Esta es la forma fuerte de inducción matemática:

Teorema\(\PageIndex{1}\): Strong Induction

Supongamos que tenemos una declaración\(P(n)\) sobre el entero\(n\). Si sabemos que

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

entonces\(P(n)\) es cierto para cada entero\(n ≥ n_0\).

Usando esto, podemos completar el ejemplo que iniciamos anteriormente. Tenemos\(a_1 = 2\) (por la condición inicial), y la hipótesis de inducción fuerte nos permite suponer que\(a_i = 2^{i−1}\) para cada entero\(i\) con\(2 ≤ i ≤ k\). Entonces, usando la relación recursiva

\[a_{k+1} = \sum_{i=1}^{k} a_i\]

vemos que

\[a_{k+1} = 2 + \sum_{i=2}^{k} 2^{i-1}\]

Probablemente aprendiste en la secundaria a sumar secuencias geométricas como esta; en particular, eso

\[\sum_{j=0}^{k} 2^{j} = 2^{k+1} - 1 \]

y podemos reescribir lo que tenemos como

\[a_{k+1} = 1 + \left( 1 + \sum_{j=1}^{k-1} 2^{j} \right) = 1 + \sum_{j=0}^{k-1} 2^{j} = 1+ (2^{(k-1)+1} - 1) = 2^k \]

Esto es precisamente lo que necesitábamos deducir, así que esto completa la prueba.

Repasemos un ejemplo más que implica una fuerte inducción. En este ejemplo, necesitaremos una fuerte inducción por una razón ligeramente diferente: necesitaremos que la afirmación sea cierta para algunos valores entre\(n_0\) y\(k\), pero no estamos necesariamente seguros de cuáles.

Ejemplo\(\PageIndex{2}\)

Shawna está construyendo una torre con lego. Demostrar que si tiene n pedazos de lego (donde\(n ≥ 1\)), y un “movimiento” consiste en pegar dos torres más pequeñas juntas en una (donde una torre puede consistir en una o más piezas de lego), entonces tomará sus\(n − 1\) movimientos para completar la torre

Solución

Caso base:\(n = 1\). La “torre” de Shawna ya está completa después de los\(n − 1 = 0\) movimientos. Esto completa la prueba del caso base.

Paso de inducción: comenzamos con la hipótesis de inducción, que cuando\(1 ≤ i ≤ k\), toma Shawna\(i − 1\) se mueve para construir una torre que contenga\(i\) piezas de lego.

Ahora queremos deducir que cuando Shawna tiene\(k + 1\) pedazos de lego, se necesitan sus\(k\) movimientos para pegarlos juntos en una sola torre. Observe que cuando haga su jugada final, debe consistir en unir dos torres más pequeñas, una de las cuales contiene\(j\) piezas de lego, y la otra contiene las\(k + 1 − j\) piezas restantes. Ambos\(j\) y\(k + 1 − j\) deben estar entre\(1\) y\(k\) (si alguna de las torres más pequeñas tuviera\(k+1\) piezas entonces la torre ya estaría completa), por lo que la hipótesis de inducción se aplica a cada una de ellas. Así, ha tomado Shawna\(j − 1\) mover para construir la torre que contiene\(j\) piezas, y\(k − j\) se mueve para construir la torre que contiene\(k − j + 1\) piezas. Junto con su jugada final, entonces, debe tomar Shawna

\((j − 1) + (k − j) + 1\)

se mueve en total para completar su torre de\(k + 1\) piezas. Ahora,

\((j − 1) + (k − j) + 1 = k\),

así que se necesitan\(k\) movimientos de Shawna para completar la torre, que es lo que queríamos deducir. Esto completa la prueba del paso inductivo.

Por Fuerte Inducción, se necesitarán\(n − 1\) movimientos de Shawna para completar una torre que contenga\(n\) bloques de lego, para cada uno\(n ≥ 1\).

Esto es bastante asombroso. Si intentáramos pasar por el argumento completo de cuántos movimientos se necesita para construir una torre con cuatro cuadras, iría algo así. Primero, construir una torre con un bloque claramente toma\(0\) movimientos; construir una torre con dos bloques claramente toma\(1\) movimiento (pegar los dos bloques juntos). Para construir una torre con tres bloques, debemos usar\(1\) mover para unir una torre de dos bloques (que tomó\(1\) movimiento para crear) con una torre de un bloque (que tomó\(0\) movimientos para crear), es decir, que usamos\(2\) movimientos por completo. Ahora, una torre de cuatro bloques se puede construir de dos maneras: usando\(1\) mover para unir dos torres de dos bloques, cada una de las cuales tomó\(1\) movimiento para hacer, para un total de\(3\) movimientos; o usando\(1\) mover para unir una torre de una cuadra (que tomó\(0\) movimientos para hacer) con una torre de tres cuadras (que tomó\(2\) movimientos para hacer), para un total de\(3\) movimientos. Entonces bajo cualquiera de los dos métodos, construir una torre de cuatro bloques toma\(3\) movimientos. Se puede ver que el argumento se complicará cada vez más a medida que\(n\) aumente, pero siempre seguirá funcionando.

No necesitaremos una inducción fuerte como tal hasta más adelante en el curso, pero la idea es un fondo útil para el siguiente tipo de inducción que veremos, lo cual es muy importante a la hora de tratar las relaciones de recurrencia: la inducción con múltiples casos base.

La inducción con múltiples casos base es muy importante para tratar secuencias definidas recursivamente como la secuencia de Fibonacci, donde cada término depende de más de uno de los términos anteriores.

Supongamos que se le pidió probar que el enésimo término de la secuencia de Fibonacci,\(f_n\), es al menos\(2^{n−2}\). Si tratamos de seguir nuestra estrategia inductiva básica, comenzaríamos observando que esto es cierto para\(f_0\):

\(f_0 = 1 ≥ 2 −2 = \dfrac{1}{4}\).

Entonces haríamos la hipótesis inductiva de que nuestra desigualdad es cierta para algunos arbitrarios\(k ≥ 0\), entonces\(f_k ≥ 2^{k−2}\). Ahora para deducir la desigualdad para\(n = k + 1\), el enfoque natural es usar la relación recursiva, que nos dice que

\(f_{k+1} = f_k + f_{k−1}\).

Podemos usar nuestra hipótesis inductiva para hacer una sustitución\(f_k\), pero ¿y qué pasa\(f_{k−1}\)? Podrías (razonablemente) argumentar en este punto que deberíamos usar una inducción fuerte, lo que nos permitirá suponer que el resultado es cierto para ambos\(f_k\) y\(f_{k−1}\), pero en realidad, ¡esto no funciona! ¿Por qué no? Bueno, el problema es que todo lo que sabemos de la secuencia de Fibonacci empieza con\(f_0\), pero si\(k = 1\) (que es la primera vez que intentamos usar inducción) entonces\(f_{k−1} = f_{−1}\), ¡que ni siquiera hemos definido! Es muy importante asegurar que en el paso inductivo, nunca hagamos que nuestra suposición retroceda demasiado, es decir, a un valor inferior\(n_0\).

Entonces, ¿cómo podemos lidiar con este problema? La solución es agregar otro caso base, para\(n = 1\). Cuando\(n = 1\), tenemos

\(f_1 = 1 ≥ 2^{1−2} = \dfrac{1}{2}\).

Ahora bien, si intentamos la inducción, en el primer paso estaremos usando el hecho de que la afirmación es cierta\(f_1\) para\(f_0\) y para probarla\(f_2\); entonces el hecho de que es verdad para\(f_1\) y nos\(f_2\) permitirá deducir por\(f_3\), y así sucesivamente. El argumento final se verá como el siguiente.

Ejemplo\(\PageIndex{3}\)

Demostrar por inducción que el\(n^{\text{th}}\) término de la secuencia de Fibonacci\(f_n\),, es al menos\(\left( \dfrac{3}{2} \right)^{n−1}\), para cada\(n ≥ 0\).

Solución

Dado que la relación recursiva para la secuencia de Fibonacci requiere los dos términos inmediatamente anteriores, requeriremos dos casos base.

Casos base: Cuando\(n = 0\), tenemos

\(f_0 = 1 ≥ \left( \dfrac{3}{2} \right)^{−1} = \dfrac{2}{3}\),

por lo que la desigualdad se sostiene\(n = 0\). Cuando\(n = 1\), tenemos

\(f_1 = 1 ≥ \left( \dfrac{3}{2} \right)^{1−1} = 1\),

por lo que la desigualdad se sostiene\(n = 1\). Esto completa la prueba de los casos base.

Paso inductivo: Comenzamos con la hipótesis inductiva (fuerte). Dejar\(k\) ser un entero arbitrario al menos tan grande como nuestro caso base más grande, entonces\(k ≥ 1\). Supongamos que por cada entero\(i\) con\(0 ≤ i ≤ k\), tenemos\(f_i ≥ \left( \dfrac{3}{2} \right)^{i−1}\).

Ahora queremos deducir que

\(f_{k+1} ≥ \left( \dfrac{3}{2} \right)^{(k+1)−1} = \left( \dfrac{3}{2} \right)^k \).

Usando la relación recursiva, lo sabemos\(f_{k+1} = f_k +f_{k−1}\). Ya que\(k ≥ 1\), tenemos\(k −1 ≥ 0\), así tanto\(k\) y\(k − 1\) satisfacer los límites en\(i\) (eso\(0 ≤ i ≤ k\)), para que podamos aplicar nuestra hipótesis inductiva a ambos\(f_k\) y\(f_{k−1}\). Por lo tanto, tenemos

\(f_{k+1} ≥ \left( \dfrac{3}{2} \right)^{k−1} + \left( \dfrac{3}{2} \right)^{k−2} = \left( \dfrac{3}{2} + 1 \right)\left( \dfrac{3}{2} \right)^{k−2} = \dfrac{5}{2} \left( \dfrac{3}{2} \right)^{k−2} = \dfrac{5}{3} \cdot \dfrac{3}{2} \left( \dfrac{3}{2} \right)^{k−2} > \left( \dfrac{3}{2} \right)^k \)

ya que\(\dfrac{5}{3} > \dfrac{3}{2}\). Esto es lo que queríamos deducir. Esto completa la prueba del paso inductivo.

Por el Principio de Inducción Matemática,\(f_n ≥ \left( \dfrac{3}{2} \right)^{n−1}\) para cada\(n ≥ 0\).

Ejercicio\(\PageIndex{1}\)

1. Demostrar por inducción que para cada uno\(n ≥ 0\), el enésimo término de la secuencia de Fibonacci no es mayor que\(2^n\).
2. La máquina de la cafetería no funciona correctamente, y solo puede poner incrementos de\($4\) o\($5\) en tu tarjeta de regalo. Demuestra por inducción que puedes obtener cualquier cantidad de dólares que sea al menos\($12\). [Pista: Deberías tener cuatro casos base.]
3. Definir una relación de recurrencia por\(a_0 = a_1 = a_2 = 1\), y\(a_n = a_{n−1} + a_{n−2} + a_{n−3}\) para\(n ≥ 3\). Demostrar por inducción que\(a_n ≤ 2^n\) para todos\(n ≥ 0\).