6.1: Secuencias definidas recursivamente

Puede estar familiarizado con el término “recursión” como técnica de programación. Proviene de la misma raíz que la palabra “repetir”, y es una técnica que implica aplicar repetidamente una definición de autorreferencia hasta llegar a algunos términos iniciales que se definen explícitamente, y luego volver a través de las aplicaciones para elaborar el resultado que queremos. Si no seguiste eso, está bien, pasaremos por la definición y algunos ejemplos específicos que deberían darte la idea.

Definición: Relación recursiva

Una secuencia\(r_1, r_2, . . . , r_n, . . .\) se define recursivamente si por cada\(n\) mayor que o igual a algún límite\(b ≥ 2\), el valor para\(r_n\) depende de al menos algunos de los valores de\(r_1, . . . , r_{n−1}\). Los valores para\(r_1, . . . , r_{b−1}\) se dan explícitamente; estos se conocen como las condiciones iniciales para la secuencia definida recursivamente. La ecuación que define\(r_n\) desde\(r_1, . . . , r_{n−1}\) se llama la relación recursiva.

Probablemente el ejemplo más conocido de una secuencia definida recursivamente es la secuencia de Fibonacci. Se llama así por un matemático italiano que introdujo la secuencia a la cultura occidental como ejemplo en un libro en el que escribió para\(1202\) abogar por el uso de números arábigos y el sistema decimal. La secuencia era conocida por los matemáticos indios ya en el\(6^{\text{th}}\) siglo.

Definición: Secuencia de Fibonacci

La secuencia de Fibonacci es la secuencia\(f_0, f_1, f_2, . . .\), definida por\(f_0 = 1\)\(f_1 = 1\), y\(f_n = f_{n−1} + f_{n−2}\) para todos\(n ≥ 2\).

Entonces en la secuencia de Fibonacci,\(f_0 = f_1 = 1\) están las condiciones iniciales, y\(f_n = f_{n−1} + f_{n−2}\) para todos\(n ≥ 2\) está la relación recursiva.

El problema habitual asociado a las secuencias definidas recursivamente, es encontrar una fórmula explícita para el\(n^{th}\) término que no requiera calcular todos los términos anteriores. Claramente, si queremos poder determinar términos que surjan más adelante en la secuencia, esto es crítico. Si tratamos de encontrar directamente el término millonésimo de una secuencia definida recursivamente, requerirá una gran cantidad de tiempo de computación y también podría requerir mucha memoria.

Cada vez que en la escuela te pedían mirar una secuencia de números, encontrar un patrón y dar el siguiente número en la secuencia, probablemente estabas elaborando una relación de recurrencia y aplicándola.

Ejemplo\(\PageIndex{1}\)

Considera la secuencia 5, 8, 11, 14. ¿Qué número debería venir después?

Solución

Consideramos las diferencias entre pares sucesivos:\(8 − 5 = 3\);\(11 − 8 = 3\);\(14 − 11 = 3\). Esto parece ser una secuencia aritmética, con la diferencia constante de\(3\) entre términos sucesivos. Entonces la secuencia se puede definir por\(a_1 = 5\) y\(a_n = a_{n−1} + 3\), para cada\(n ≥ 2\). Nos pidieron\(a_5\), y eso lo sabemos\(a_4 = 14\), entonces\(a_5 = a_4 + 3 = 14 + 3 = 17\).

Aquí hay un ejemplo un poco más complicado:

Ejemplo\(\PageIndex{2}\)

Considera la secuencia\(3\),\(6\),\(11\),\(18\),\(27\). ¿Qué número debería venir después?

Solución

De nuevo, considere las diferencias entre términos sucesivos:\(6 − 3 = 3\);\(11 − 6 = 5\);;\(18−11 = 7\);\(27−18 = 9\). Estas diferencias no son constantes, pero sí siguen un patrón predecible: son los números impares (comenzando en\(3\) y aumentando). Entonces la secuencia se puede definir por\(a_1 = 3\) y an =\(a_{n−1} + (2n − 1)\), para cada\(n ≥ 2\). Nos pidieron\(a_6\), y eso lo sabemos\(a_5 = 27\), entonces\(a_6 = a_5 + 2(6) − 1 = 27 + 11 = 38\).

Este ejemplo muestra que la relación de recurrencia puede depender de n, así como de los valores de los términos anteriores. (Aunque no lo dijimos explícitamente en nuestra definición, está implícito porque\(n − 1\) es el número de términos anteriores\(r_n\) del que depende; podríamos calcular\(n\) como\(a^0_1 + a^0_2 + . . . + a^0_{n−1} + 1\).)

Veamos un ejemplo más.

Ejemplo\(\PageIndex{3}\)

El banco de Stavroula paga\(1 \%\) intereses (compuestos anualmente), y le cobra una tarifa de servicio\($10\) anual para mantener la cuenta. La tasa se cobra al inicio del año, y los intereses se calculan sobre el saldo al cierre del año. Si empieza con un saldo de\($2000\), ¿está ganando dinero o perdiendo dinero? Si sus padres le configuran esta cuenta y no se le permite tocarla, ¿cuánto dinero habrá en la cuenta después de siete años?

Solución

Vemos que el término inicial es\(r_0 = 2000\). Vamos a usar\(r_0\) como primer término, porque entonces el valor de su cuenta tras\(1\) año será\(r_1\); después de dos años será\(r_2\); y después de siete años lo será\(r_7\). Esto solo hace que sea un poco más fácil hacer un seguimiento de lo que pretendemos averiguar.

Si desempacamos el lenguaje financiero, nos está diciendo que cada año, el banco toma\($10\) de la cuenta de Stavroula al inicio del año. Entonces al final del año, el banco agrega\(1 \%\) de lo que esté en la cuenta de Stavroula, a su cuenta. Esto puede ser representado por la siguiente relación de recurrencia:\(r_n = r_{n−1} − 10 + .01(r_{n−1} − 10)\) para cada\(n ≥ 1\), lo que simplifica a\(r_n = 1.01(r_{n−1} − 10)\). Lógicamente, estará ganando dinero si el\(1 \%\) que gana en intereses, excede la tarifa de servicio de\($10\), así que si gana dinero en el primer año, seguirá ganando dinero; mientras que si pierde dinero en el primer año, seguirá perdiendo dinero después de eso. Entonces, para responder a la primera pregunta, vamos a resolver\(r_1 = 1.01(r_0 −10) = 1.01(1990) = 2009.9\). Stavroula está ganando dinero.

Para responder a la segunda pregunta, a menos que hayamos logrado encontrar una fórmula explícita para\(r_n\) (que aún no sabemos cómo hacer), necesitamos calcular\(r_2\),,\(r_3\),\(r_4\)\(r_5\),\(r_6\), y\(r_7\). Sería razonable suponer que el banco redondea sus cálculos al centavo más cercano cada año, y continúa con el valor redondeado, pero debido a que esto creará un error que se agravará en comparación con resolver nuestra relación de recurrencia explícitamente (que aprenderemos más adelante a hacer), vamos a realizar un seguimiento de los valores exactos en su lugar. Tenemos

\( \begin{equation}\begin{split} r_2 &= 1.01(2009.9 − 10) = 2019.899; \\ r_3&= 1.01(2009.899) = 2029.99799; \\ r_4&= 1.01(2019.99799) = 2040.1979699; \\ r_5&= 1.01(2030.1979699) = 2050.499949599; \\ r_6&= 1.01(2040.499949599) = 2060.90494909499; \text{ and} \\ r_7&= 1.01(2050.90494909499) = 2071.4139985859399 \end{split} \end{equation} \)

Entonces, al final de siete años, Stavroula tiene\($2071.41\).

Ejercicio\(\PageIndex{1}\)

Resolver los siguientes problemas sobre las relaciones de recurrencia.

1. Considera la secuencia\(4\),\(9\),\(19\),\(39\). Dar una relación de recurrencia que describa esta secuencia, y encontrar el siguiente término en la secuencia.
2. Utilice la relación de recurrencia para la secuencia de Fibonacci para encontrar\(f_6\).
3. Si la cuota anual en la cuenta bancaria de Stavroula del Ejemplo 6.1.3 es\($20\) en lugar de\($10\), ¿está ganando dinero o perdiendo dinero?