3.6: Inducción Matemática - La Forma Fuerte

Es posible que hayas oído hablar de los números de Fibonacci. Ocurren con frecuencia en matemáticas y ciencias de la vida. ¡Incluso se han aplicado para estudiar el mercado de valores! Los números de Fibonacci forman una secuencia cada término de la cual, excepto los dos primeros, es la suma de los dos números anteriores. Matemáticamente, si denotamos el número\(n\) th Fibonacci\(F_n\), entonces\[F_n = F_{n-1} + F_{n-2}. \label{eqn:FiboRecur}\] Esto se llama la relación de recurrencia para\(F_n\).

Algunos estudiantes tienen problemas para usar\ ref {eqn:fiborecur}: no estamos agregando\(n-1\) y\(n-2\). Los subíndices solo indican las ubicaciones dentro de la secuencia de Fibonacci. De ahí,\(F_1\) significa el primer número de Fibonacci,\(F_2\) el segundo número de Fibonacci, y así sucesivamente. Compare esto con dejar caer diez números en diez cajas, y cada caja está etiquetada con los números del 1 al 10. Usemos\(a_i\) para denotar el valor en el cuadro\(i\) th. Cuando decimos\(a_7\), no nos referimos al número 7. En cambio, nos referimos al número almacenado en el recuadro 7. Expresado en palabras, la relación de recurrencia\ ref {eqn:Fiborecur} nos dice que el\(n\) número de Fibonacci es la suma de los números\((n-1)\)\((n-2)\) th y th Fibonacci. Esto es fácil de recordar: sumamos los dos últimos números de Fibonacci para obtener el siguiente número de Fibonacci.

La relación de recurrencia implica que necesitamos comenzar con dos valores iniciales. A menudo comenzamos con\(F_0=0\) (imagen\(F_0\) como el número cero de Fibonacci, el número almacenado en el Cuadro 0) y\(F_1=1\). Combinamos la relación de recurrencia para\(F_n\) y sus valores iniciales juntos en una definición:

\ [F_0=0,\ quad F_1=1,\ qquad
F_n = F_ {n-1} + F_ {n-2},\ quad\ mbox {for} n\ geq2\ nonumber\]

Tenemos que especificar que la relación de recurrencia es válida sólo cuando\(n\geq2\), porque este es el valor más pequeño del\(n\) que podemos usar la relación de recurrencia. ¿Qué pasa si quieres encontrar\(F_1\) usando esta fórmula? Obtendrás\(F_1=F_0+F_{-1}\), ¡pero no\(F_{-1}\) está definido!

La suma de los números cero y los primeros números de Fibonacci nos dan el segundo número de Fibonacci:\[F_2 = F_1 + F_0 = 1 + 0 = 1. \nonumber\] Continuando de esta manera, encontramos\[ \begin{array}{lclclcl} F_3 &=& F_2+F_1 &=& 1+1 &=& 2, \\ F_4 &=& F_3+F_2 &=& 2+1 &=& 3, \\ F_5 &=& F_4+F_3 &=& 3+2 &=& 5, \\ F_6 &=& F_5+F_4 &=& 5+3 &=& 8, \\ \hfil\vdots&& \hfil\vdots && \hfil\vdots && \vdots \end{array} \nonumber\] Siguiendo este patrón, ¿cuáles son los valores de\(F_7\) y\(F_8\)?

Los números de Fibonacci disfrutan de muchas propiedades interesantes, y hay numerosos resultados en relación con los números de Fibonacci. Como entrante, considera el inmueble\[F_n < 2^n, \qquad n\geq1. \nonumber\] ¿Cómo lo probaríamos por inducción?

Ya que queremos demostrar que la desigualdad es para todos\(n\geq1\), debemos verificar el caso de\(n=1\) en el paso base. Cuando\(n=1\), tenemos\(F_1=1\) que es, por supuesto, menos que\(2^1=2\). En la hipótesis inductiva, asumimos que la desigualdad se mantiene cuando\(n=k\) para algún entero\(k\geq1\); es decir, asumimos\[F_k < 2^k \nonumber\] para algún entero\(k\geq1\). A continuación, queremos demostrar que la desigualdad aún se mantiene cuando\(n=k+1\). Así que tenemos que demostrar que\[F_{k+1} < 2^{k+1}. \nonumber\]

Para hacer uso de la hipótesis inductiva, es necesario aplicar la relación de recurrencia de los números de Fibonacci. Nos dice que\(F_{k+1}\) es la suma de los dos números anteriores de Fibonacci; es decir,\[F_{k+1} = F_k + F_{k-1}. \nonumber\] Lo único que sabemos de la hipótesis inductiva es\(F_k < 2^k\). Entonces, tal como está, no nos habla mucho sobre\(F_{k+1}\).

Un remedio es asumir en la hipótesis inductiva que la desigualdad también sostiene cuando\(n=k-1\); es decir, también asumimos que\[F_{k-1} < 2^{k-1}. \nonumber\] Por lo tanto, a diferencia de todos los problemas que hemos visto hasta ahora, el paso inductivo en este problema se basa en los dos últimos\(n\) valores en lugar de solo uno. En cuanto a dominó, imagina que son tan pesados que necesitamos el peso combinado de dos dominó para derribar al siguiente. Entonces\[F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} = 2^{k-1}(2+1) < 2^{k-1} \cdot 2^2 = 2^{k+1}, \nonumber\] que completará la inducción. Esta inducción modificada se conoce como la forma fuerte de inducción matemática. En contraste, llamamos a la inducción matemática ordinaria la forma débil de inducción.

¡La prueba aún tiene una falla menor! Para poder utilizar la hipótesis inductiva en la relación de recurrencia\[F_{k+1} = F_k + F_{k-1}, \nonumber\] ambos subíndices\(k\) y\(k-1\) debe ser al menos 1, porque el enunciado lo reclama\(F_n < 2^n\) para todos\(n\geq1\). Esto significa que necesitamos\(k\geq2\). En consecuencia, en el paso base, tenemos que asumir que la desigualdad se mantiene para al menos los dos primeros valores de\(n\).

En cuanto al efecto dominó, comienza en la reacción en cadena de los dominó que caen\(k=2\). Tenemos que asegurarnos de que caigan los dos primeros dominó, para que su peso combinado derribe al tercer dominó. Entonces el peso combinado del segundo y el tercer dominó golpeará al cuarto dominó. La reacción en cadena se prolongará indefinidamente.

Simbólicamente, la inducción matemática ordinaria se basa en la implicación\(P(k) \Rightarrow P(k+1)\). A veces,\(P(k)\) por sí sola no es suficiente para probar\(P(k+1)\). En el caso de probar\(F_n < 2^n\), en realidad\[[P(k-1) \wedge P(k)] \Rightarrow P(k+1). \nonumber\] usamos Necesitamos asumir en la hipótesis inductiva que el resultado es verdadero cuando\(n=k-1\) y\(n=k\).

De manera más general, en la fuerte forma de inducción matemática, podemos usar tantos casos previos como nos guste probar\(P(k+1)\).

Forma Fuerte de Inducción Matemática. Para demostrar que eso\(P(n)\) es cierto para todos\(n \geq n_0\), sigue estos pasos:

1. Verificar que\(P(n)\) sea cierto para algunos valores pequeños de\(n\geq n_0\).
2. Supongamos que eso\(P(n)\) es cierto\(n=n_0,n_0+1,\ldots,k\) para algún entero\(k\geq n^*\).
3. Demostrar que también\(P(k+1)\) es cierto.

La idea detrás del paso inductivo es demostrar que\[[\,P(n_0)\wedge P(n_0+1)\wedge\cdots\wedge P(k-1)\wedge P(k)\,] \Rightarrow P(k+1). \nonumber\] es posible que no necesitemos usar todos\(P(n_0),P(n_0+1),\ldots,P(k-1),P(k)\). De hecho, puede que solo necesitemos los últimos de ellos, por ejemplo,\(P(k-3),P(k-2),P(k-1)\) y\(P(k)\). El número de casos previos requeridos para establecer nos\(P(k+1)\) indica cuántos casos iniciales tenemos que verificar en el paso base. No sabemos cuántos necesitamos hasta el paso inductivo. Por ello, es prudente comenzar con un borrador.

Ejemplo\(\PageIndex{1}\label{eg:induct3-01}\)

\(F_n<2^n\)Demuéstralo para todos\(n\geq1\).

Comentario

Ya hemos trabajado en el borrador en la discusión anterior. Sabemos que necesitamos verificar los dos primeros\(n\) valores en el paso base, y asumir que la desigualdad se mantiene durante al menos dos casos.

Responder

Proceder por inducción encendido\(n\). Cuando\(n=1\) y\(n=2\), encontramos\[\displaylines{ F_1 = 1 < 2 = 2^1, \cr F_2 = 1 < 4 = 2^2. \cr} \nonumber\] Por lo tanto, la desigualdad sostiene cuándo\(n=1, 2\). Supongamos que se sostiene para\(n=1,2,\ldots,k\), donde\(k\geq2\). En particular, tenemos\[F_k < 2^k, \qquad\mbox{and}\qquad F_{k-1} < 2^{k-1}, \nonumber\] donde\(k\geq2\). Entonces\[F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} = 2^{k-1} (2+1) < 2^{k-1}\cdot 2^2 = 2^{k+1}. \nonumber\] De ahí, la desigualdad aún se mantiene cuando\(n=k+1\), lo que completa la inducción.

La relación de recurrencia se puede utilizar para definir una secuencia. Por ejemplo, si la secuencia\(\{a_n\}_{n=1}^\infty\) se define recursivamente por\[a_n = 3 a_{n-1} - 2 \qquad \mbox{for } n\geq2, \nonumber\] con\(a_1=4\), entonces la\[\displaylines{ a_2 = 3a_1 - 2 = 3\cdot4-2 = 10, \cr a_3 = 3a_2 - 2 = 3\cdot10-2 = 28. \cr} \nonumber\] identidad que involucra tales secuencias a menudo se puede probar por medio de inducción.

Ejemplo\(\PageIndex{2}\label{eg:induct3-02}\)

La secuencia\(\{b_n\}_{n=1}^\infty\) se define como\[b_1 = 5, \quad b_2 = 13, \qquad b_n = 5b_{n-1} - 6b_{n-2} \quad\mbox{for } n\geq3. \nonumber\] Demostrar eso\(b_n = 2^n+3^n\) para todos\(n\geq1\).

Responder

Proceder por inducción encendido\(n\). Cuando\(n=1\), la fórmula propuesta para\(b_n\) dice\(b_1=2+3=5\), que concuerda con el valor inicial\(b_1=5\). Cuando\(n=2\), la fórmula propuesta reclama\(b_2=4+9=13\), lo que nuevamente concuerda con la definición\(b_2=13\). Supongamos que la fórmula es válida\(n=1,2,\ldots,k\) para algún entero\(k\geq2\). En particular,\[b_k = 2^k+3^k, \qquad\mbox{and}\qquad b_{k-1} = 2^{k-1}+3^{k-1}. \nonumber\] supongamos Queremos demostrar que la fórmula sigue funcionando cuando\(n=k+1\). En otras palabras, queremos mostrar que\[b_{k+1} = 2^{k+1}+3^{k+1}.\nonumber\] Usando la relación de recurrencia y la hipótesis inductiva, encontramos\[\begin{array}{r c l} b_{k+1} &=& 5b_k - 6b_{k-1} \\ &=& 5(2^k+3^k)-6(2^{k-1}+3^{k-1}) \\ &=& 5\cdot2^k+5\cdot3^k-6\cdot2^{k-1}-6\cdot3^{k-1} \\ &=& 5\cdot2^k+5\cdot3^k-2\cdot3\cdot2^{k-1}-2\cdot3\cdot3^{k-1} \\ &=& 5\cdot2^k+5\cdot3^k-3\cdot2^k-2\cdot3^k \\ &=& 2\cdot2^k+3\cdot3^k \\ &=& 2^{k+1}+3^{k+1} \end{array} \nonumber\] cuál es lo que queremos establecer. Esto completa la inducción, y de ahí, la afirmación de que\(b_n = 2^n+3^n\).

ejercicio práctico\(\PageIndex{1}\label{he:induct3-01}\)

La secuencia\(\{c_n\}_{n=1}^\infty\) se define como\[c_1 = 7, \quad b_2 = 29, \qquad c_n = 5b_{n-1} - 6b_{n-2} \quad\mbox{for } n\geq3. \nonumber\] Probar eso\(c_n = 5\cdot3^n-4\cdot2^n\) para todos los enteros\(n\geq1\).

Ejemplo\(\PageIndex{3}\label{eg:induct3-03}\)

Mostrar que todos los enteros se\(n\geq24\) pueden expresar como\(4x+9y\) para algunos enteros\(x,y\geq0\).

Definición

La expresión\(4x+9y\) se denomina combinación lineal de 4 y 9,\(x\) y\(y\) se denominan los coeficientes de la combinación lineal.

Comentario

Queremos demostrar que cualquier entero suficientemente grande\(n\) puede escribirse como una combinación lineal de 4 y 9 con coeficientes no negativos. Este problema se llama el problema del sello postal por la razón obvia: ¿podemos usar solo sellos de 4 centavos y 9 centavos para obtener un franqueo de\(n\) -cent para todos los enteros\(n\geq24\)? No es muy sorprendente, también se le llama el problema del cambio de dinero (imagínese reemplazar los sellos por monedas).

Comentario

El espíritu detrás de la inducción matemática (formas débiles y fuertes) está haciendo uso de lo que sabemos sobre un problema de menor tamaño. En la forma débil, utilizamos el resultado de\(n=k\) para establecer el resultado para\(n=k+1\). En la forma fuerte, utilizamos algunos de los resultados de\(n=k,k-1,k-2,\ldots\,\) para establecer el resultado para\(n=k+1\).

Discusión

Veamos primero el paso inductivo, en el que queremos mostrar que podemos escribir\(k+1\) como una combinación lineal de 4 y 9. El paso clave de cualquier prueba de inducción es relacionar el caso de\(n=k+1\) un problema con un tamaño más pequeño (por lo tanto, con un valor menor en\(n\)).

Imagina que quieres enviar una carta que requiera un franqueo\((k+1)\) -cent, y puedes usar solo sellos de 4 centavos y 9 centavos. Primero podrías poner un sello de 4 centavos. Entonces aún necesitas llegar con el franqueo restante de\((k+1)-4=k-3\) centavos. Si pudieras usar sellos de 4 y 9 centavos para componer el franqueo restante\((k-3)\), el problema está resuelto. Por lo tanto, en la hipótesis inductiva, hay que asumir que se puede hacer cuando\(n=k-3\).

Para que todo el argumento funcione,\(k-3\) tiene que estar dentro del rango de los\(n\) -valores que consideramos. Entonces necesitamos\(k-3\geq24\); es decir, queremos\(k\geq27\). En consecuencia, tenemos que verificar el reclamo para\(n=24,25,26,27\) en el paso base.

Solución

Proceder por inducción encendido\(n\). Encontramos\[\begin{aligned} 24 &=& 4\cdot6 + 9\cdot0, \\ 25 &=& 4\cdot4 + 9\cdot1, \\ 26 &=& 4\cdot2 + 9\cdot2, \\ 27 &=& 4\cdot0 + 9\cdot3. \end{aligned} \nonumber\] Por lo tanto, el reclamo es cierto cuando\(n=24,25,26,27\). Supongamos que es cierto cuando\(n=24,25,\ldots,k\) para algún entero\(k\geq27\). En particular, ya que\(k-3\geq24\), esta suposición asegura que\[k-3 = 4x+9y \nonumber\] para algunos enteros no negativos\(x\) y\(y\). De ello se deduce que\[\begin{array}{r c l} k+1 &=& 4+(k-3) \\ &=& 4+4x+9y \\ &=& 4(1+x)+9y, \end{array} \nonumber\] donde\(1+x\) y\(y\) son enteros no negativos. Esto demuestra que la afirmación sigue siendo cierta cuando\(n=k+1\), con ello se completa la inducción.

Ejercicio práctico\(\PageIndex{2}\label{he:induct3-02}\)

Mostrar que todos los enteros se\(n\geq2\) pueden expresar como\(2x+3y\) para algunos enteros no negativos\(x\) y\(y\).

Resumen y revisión

• Si, en el paso inductivo, necesitamos usar más de una instancia previa de la afirmación que estamos probando, podemos usar la forma fuerte de la inducción.
• En tal caso, tenemos que modificar la hipótesis inductiva para incluir más casos en el supuesto.
• También necesitamos verificar más casos en el paso base.
• Por último, necesitamos reescribir toda la prueba para hacerla coherente.

Ejercicios 3.6

Ejercicio\(\PageIndex{1}\label{ex:induct3-01}\)

Utilice la inducción matemática para probar la identidad\[F_1^2+F_2^2+F_3^2+\cdots+F_n^2 = F_n F_{n+1} \nonumber\] de cualquier entero\(n\geq1\).

Ejercicio\(\PageIndex{2}\label{ex:induct3-02}\)

Utilice la inducción para probar la siguiente identidad para todos los enteros\(n\geq1\):\[F_1+F_3+F_5+\cdots+F_{2n-1} = F_{2n}. \nonumber\]

Ejercicio\(\PageIndex{3}\label{ex:induct3-03}\)

Usa la inducción para demostrarlo\[\frac{F_1}{F_2F_3} + \frac{F_2}{F_3F_4} + \frac{F_3}{F_4F_5} + \cdots + \frac{F_{n-2}}{F_{n-1}F_n} = 1 - \frac{1}{F_n} \nonumber\] para todos los enteros\(n\geq3\).

Ejercicio\(\PageIndex{4}\label{ex:induct3-04}\)

Usa la inducción para demostrar que cualquier entero\(n\geq8\) puede escribirse como una combinación lineal de 3 y 5 con coeficientes no negativos.

Ejercicio\(\PageIndex{5}\label{ex:induct3-05}\)

Un equipo de fútbol puede anotar un gol de campo por 3 puntos o ¹ un touchdown (con conversión) por 7 puntos. Demostrar que, para cualquier entero\(n\geq12\), es posible que un equipo de futbol anote\(n\) puntos con goles de campo y touchdowns.

Ejercicio\(\PageIndex{6}\label{ex:induct3-06}\)

Un país insular sólo emite monedas de 1 centavo, 5 y 9 centavos. Debido al desabasto en cobre, todas las monedas de 1 centavo fueron recordadas. Demuestre que, usando solo monedas de 5 y 9 centavos, uno puede pagar una compra de\(n\) -cent por cualquier\(n\geq32\).

Ejercicio\(\PageIndex{7}\label{ex:induct3-07}\)

La secuencia\(\{b_n\}_{n=1}^\infty\) se define recursivamente por\[b_n = 3 b_{n-1} - 2 \qquad \mbox{for } n\geq2, \nonumber\] con\(b_1=4\). Usa la inducción para demostrarlo\(b_n=3^n+1\) para todos\(n\geq1\).

Ejercicio\(\PageIndex{8}\label{ex:induct3-08}\)

La secuencia\(\{c_n\}_{n=1}^\infty\) se define recursivamente como\[c_1=3, \quad c_2=-9, \qquad c_n = 7c_{n-1} - 10c_{n-2}, \quad\mbox{for } n\geq3. \nonumber\] Usar inducción para mostrar eso\(c_n = 4\cdot2^n-5^n\) para todos los números enteros\(n\geq1\).

Ejercicio\(\PageIndex{9}\label{ex:induct3-09}\)

La secuencia\(\{d_n\}_{n=1}^\infty\) se define recursivamente como\[d_1=2, \quad d_2=56, \qquad d_n = d_{n-1} + 6d_{n-2}, \quad\mbox{for } n\geq3. \nonumber\] Usar inducción para mostrar eso\(d_n = 5(-2)^n+4\cdot3^n\) para todos los números enteros\(n\geq1\).

Ejercicio\(\PageIndex{10}\label{ex:induct3-10}\)

La secuencia\(\{a_n\}_{n=1}^\infty\) se define recursivamente como\[a_1=2, \quad a_2=4, \qquad a_n = 2a_{n-1} + 3a_{n-2}, \quad\mbox{for } n\geq3. \nonumber\] Usar inducción para mostrar eso\(a_n > \left(\frac{5}{2}\right)^n\) para cualquier entero\(n\geq4\).

---

1. Si bien es posible que un equipo anote 2 puntos por un seguro u 8 puntos por un touchdown con una conversión de dos puntos, no consideraríamos estas posibilidades en esta versión simplificada de un partido de fútbol real. ↩