2.4: Resolver relaciones de recurrencia

Template:MathJaxLevin

¡Investiga!

Considerar la relación de recurrencia

\ begin {ecuación*} a_n = 5a_ {n-1} - 6a_ {n-2}. \ end {ecuación*}

1. Qué secuencia obtienes si las condiciones iniciales son\(a_0 = 1\text{,}\)\(a_1 = 2\text{?}\) Dar una fórmula cerrada para esta secuencia.
2. Qué secuencia obtienes si las condiciones iniciales son\(a_0 = 1\text{,}\)\(a_1 = 3\text{?}\) Dar una fórmula cerrada.
3. Qué pasaría si\(a_0 = 2\) y\(a_1 = 5\text{?}\) Encuentra una fórmula cerrada.

Hemos visto que muchas veces es más fácil encontrar definiciones recursivas que fórmulas cerradas. Por suerte para nosotros, existen algunas técnicas para convertir definiciones recursivas a fórmulas cerradas. Hacerlo se llama resolver una relación de recurrencia. Recordemos que la relación de recurrencia es una definición recursiva sin las condiciones iniciales. Por ejemplo, la relación de recurrencia para la secuencia de Fibonacci es\(F_n = F_{n-1} + F_{n-2}\text{.}\) (Esto, junto con las condiciones iniciales\(F_0 = 0\) y\(F_1 = 1\) dar toda la definición recursiva para la secuencia.)

Ejemplo\(\PageIndex{1}\)

Encuentre una relación de recurrencia y condiciones iniciales para\(1, 5, 17, 53, 161, 485\ldots\text{.}\)

Solución

Encontrar la relación de recurrencia sería más fácil si tuviéramos algún contexto para el problema (como la Torre de Hanoi, por ejemplo). Ay, sólo tenemos la secuencia. Recuerda, la relación de recurrencia te indica cómo llegar de términos anteriores a términos futuros. ¿Qué está pasando aquí? Podríamos ver las diferencias entre términos:\(4, 12, 36, 108, \ldots\text{.}\) Notice that these are growing by a factor of 3. Is the original sequence as well? \(1\cdot 3 = 3\text{,}\) \(5 \cdot 3 = 15\text{,}\) \(17 \cdot 3 = 51\) and so on. It appears that we always end up with 2 less than the next term. Aha!

Entonces\(a_n = 3a_{n-1} + 2\) is our recurrence relation and the initial condition is \(a_0 = 1\text{.}\)

Vamos a tratar de resolver estas relaciones de recurrencia. Con esto nos referimos a algo muy similar a resolver ecuaciones diferenciales: queremos encontrar una función de\(n\) (una fórmula cerrada) que satisfaga la relación de recurrencia, así como la condición inicial. ² Las relaciones de recurrencia a veces se denominan ecuaciones de diferencia, ya que pueden describir la diferencia entre términos y esto resalta aún más la relación con las ecuaciones diferenciales. Al igual que para las ecuaciones diferenciales, encontrar una solución puede ser complicado, pero verificar que la solución sea correcta es fácil.

Ejemplo\(\PageIndex{2}\)

Comprobar que\(a_n = 2^n + 1\) es una solución a la relación de recurrencia\(a_n = 2a_{n-1} - 1\) con\(a_1 = 3\text{.}\)

Solución

Primero, es fácil verificar el estado inicial:\(a_1\) should be \(2^1 + 1\) according to our closed formula. Indeed, \(2^1 + 1 = 3\text{,}\) which is what we want. To check that our proposed solution satisfies the recurrence relation, try plugging it in.

\ begin {align*} 2a_ {n-1} - 1\ amp = 2 (2^ {n-1} + 1) - 1\\\ amp = 2^n + 2 - 1\\ amp = 2^n +1\\\ amp = a_n.\ end {align*}

¡Eso es lo que dice nuestra relación de recurrencia! Tenemos una solución.

A veces podemos ser inteligentes y resolver una relación de recurrencia por inspección. Generamos la secuencia usando la relación de recurrencia y hacemos un seguimiento de lo que estamos haciendo para que podamos ver cómo saltar a encontrar solo el\(a_n\) término. Aquí hay dos ejemplos de cómo podrías hacer eso.

Telescópico se refiere al fenómeno cuando muchos términos en una gran suma se cancelan, por lo que la suma “telescopios”. Por ejemplo:

\ begin {ecuación*} (2 - 1) + (3 - 2) + (4 - 3) +\ cdots + (100 - 99) + (101 - 100) = -1 + 101\ end {ecuación*}

porque cada tercer término se ve así:\(2 + -2 = 0\text{,}\) y luego\(3 + -3 = 0\) y así sucesivamente.

Podemos usar este comportamiento para resolver relaciones de recurrencia. Aquí hay un ejemplo.

Ejemplo\(\PageIndex{3}\)

Resolver la relación de recurrencia\(a_n = a_{n-1} + n\) con término inicial\(a_0 = 4\text{.}\)

Solución

Para tener una idea de la relación de recurrencia, escriba los primeros términos de la secuencia:\(4, 5, 7, 10, 14, 19, \ldots\text{.}\) Look at the difference between terms. \(a_1 - a_0 = 1\) and \(a_2 - a_1 = 2\) and so on. The key thing here is that the difference between terms is \(n\text{.}\) We can write this explicitly: \(a_n - a_{n-1} = n\text{.}\) Of course, we could have arrived at this conclusion directly from the recurrence relation by subtracting \(a_{n-1}\) from both sides.

Ahora usa esta ecuación una y otra vez, cambiando\(n\) each time:

\ begin {align*} a_1 - a_0\ amp = 1\\ a_2 - a_1\ amp = 2\\ a_3 - a_2\ amp = 3\\ vdots\ quad\ amp\ quad\ vdots\\ a_n - a_ {n-1}\ amp = n.\ end {align*}

Sumar todas estas ecuaciones juntas. En el lado derecho, obtenemos la suma\(1 + 2 + 3 + \cdots + n\text{.}\) We already know this can be simplified to \(\frac{n(n+1)}{2}\text{.}\) What happens on the left-hand side? We get

\ begin {ecuación*} (a_1 - a_0) + (a_2 - a_1) + (a_3 - a_2) +\ cdots (a_ {n-1} - a_ {n-2}) + (a_n - a_ {n-1}). \ end {ecuación*}

Esta suma telescopios. Nos quedamos con sólo el\(-a_0\) from the first equation and the \(a_n\) from the last equation. Putting this all together we have \(-a_0 + a_n = \frac{n(n+1)}{2}\) or \(a_n = \frac{n(n+1)}{2} + a_0\text{.}\) But we know that \(a_0 = 4\text{.}\) So the solution to the recurrence relation, subject to the initial condition is

\ begin {ecuación*} a_n =\ frac {n (n+1)} {2} + 4. \ end {ecuación*}

(Ahora que sabemos eso, debemos notar que la secuencia es el resultado de sumar 4 a cada uno de los números triangulares.)

El ejemplo anterior muestra una manera de resolver las relaciones de recurrencia de la forma\(a_n = a_{n-1} + f(n)\) donde\(\sum_{k = 1}^n f(k)\) tiene una fórmula cerrada conocida. Si reescribes la relación de recurrencia como\(a_n - a_{n-1} = f(n)\text{,}\) y luego sumas todas las diferentes ecuaciones con un\(n\) rango entre 1 y\(n\text{,}\) el lado izquierdo siempre te dará\(a_n - a_0\text{.}\) El lado derecho será por eso\(\sum_{k = 1}^n f(k)\text{,}\) que necesitamos conocer la fórmula cerrada para esa suma.

Sin embargo, el telescopio no nos ayudará con una recursión como\(a_n = 3a_{n-1} + 2\) ya que el lado izquierdo no se telescopiará. Tendrás\(-3a_{n-1}\)'s pero solo uno\(a_{n-1}\text{.}\) Sin embargo, todavía podemos ser inteligentes si usamos iteración.

Ya hemos visto un ejemplo de iteración cuando encontramos la fórmula cerrada para secuencias aritméticas y geométricas. La idea es, iteramos el proceso de encontrar el siguiente término, comenzando con la condición inicial conocida, hasta que tengamos\(a_n\text{.}\) Entonces simplificamos. En el ejemplo de secuencia aritmética, simplificamos multiplicando\(d\) por el número de veces que lo agregamos\(a\) cuando llegamos\(a_n\text{,}\) a para llegar de\(a_n = a + d + d + d + \cdots + d\) a\(a_n = a + dn\text{.}\)

Para ver cómo funciona esto, pasemos por el mismo ejemplo que usamos para telescopiar, pero esta vez usemos iteración.

Ejemplo\(\PageIndex{4}\)

Usar iteración para resolver la relación de recurrencia\(a_n = a_{n-1} + n\) con\(a_0 = 4\text{.}\)

Contestar

Nuevamente, comience por anotar la relación de recurrencia cuando\(n = 1\text{.}\) This time, don't subtract the \(a_{n-1}\) terms to the other side:

\ begin {ecuación*} a_1 = a_0 + 1. \ end {ecuación*}

Ahora\(a_2 = a_1 + 2\text{,}\) but we know what \(a_1\) is. By substitution, we get

\ begin {ecuación*} a_2 = (a_0 + 1) + 2. \ end {ecuación*}

Ahora ve a\(a_3 = a_2 + 3\text{,}\) using our known value of \(a_2\text{:}\)

\ begin {ecuación*} a_3 = ((a_0 + 1) + 2) + 3. \ end {ecuación*}

Notamos un patrón. Cada vez, tomamos el término anterior y agregamos el índice actual. Entonces

\ begin {ecuación*} a_n = ((((a_0 + 1) +2) +3) +\ cdots + n-1) + n.\ final {ecuación*}

Términos de reagrupación, notamos que\(a_n\) is just \(a_0\) plus the sum of the integers from \(1\) to \(n\text{.}\) So, since \(a_0 = 4\text{,}\)

\ begin {ecuación*} a_n = 4 +\ frac {n (n+1)} {2}. \ end {ecuación*}

Por supuesto que en este caso todavía necesitábamos saber fórmula para la suma de\(1,\ldots,n\text{.}\) Vamos a intentar iteración con una secuencia para la que telescopiarse no funciona.

Ejemplo\(\PageIndex{5}\)

Resolver la relación de recurrencia\(a_n = 3a_{n-1} + 2\) sujeta a\(a_0 = 1\text{.}\)

Contestar

Nuevamente, iteramos la relación de recurrencia, construyendo hasta el índice\(n\text{.}\)

\ begin {alinear*} a_1\ amp = 3a_0 + 2\ a_2\ amp = 3 (a_1) + 2 = 3 (3a_0 + 2) + 2\\ a_3\ amp = 3 [a_2] + 2 = 3 [3 (3a_0 + 2) + 2] + 2\\ vdots\ amp\ qquad\ vdots\ qquad\ vdots\ qquad\ vdots\\ a_n\ amp = 3 (a_ {n-1}) + 2 = 3 (3 (3 (3\ cdots (3a_0 + 2) + 2) + 2)\ cdots + 2) + 2. \ end {alinear*}

Es difícil ver lo que está pasando aquí porque tenemos que distribuir todos esos 3's Vamos a intentarlo de nuevo, esta vez simplificando un poco a medida que avanzamos.

\ begin {alinear*} a_1\ amp = 3a_0 + 2\ a_2\ amp = 3 (a_1) + 2 = 3 (3a_0 + 2) + 2 = 3^2a_0 + 2\ cdot 3 + 2\\ a_3\ amp = 3 [a_2] + 2 = 3 [3^2a_0 + 2\ cdot 3 + 2] + 2 = 3^3 a_0 + 2\ cdot 3^2 + 2\ cdot 3 + 2\\\ vdots\ amp\ qquad\ quad\ vdots\ hspace {2in}\ vdots\\ a_n\ amp = 3 (a_ {n-1}) + 2 = 3 (3^ {n-1} a_0 + 2\ cdot 3^ {n-2} +\ cdots +2) + 2\\\ amp\ qquad\ qquad = 3^n a_0 + 2\ cdot 3^ {n-1} + 2\ cdot 3^ {n-2} +\ cdots + 2\ cdot 3 + 2. \ end {alinear*}

Ahora simplificamos. \(a_0 = 1\text{,}\) so we have \(3^n + \langle\text{stuff}\rangle\text{.}\) Note that all the other terms have a 2 in them. In fact, we have a geometric sum with first term \(2\) and common ratio \(3\text{.}\) We have seen how to simplify \(2 + 2\cdot 3 + 2 \cdot 3^2 + \cdots + 2\cdot 3^{n-1}\text{.}\) We get \(\frac{2-2\cdot 3^n}{-2}\) which simplifies to \(3^n - 1\text{.}\) Putting this together with the first \(3^n\) term gives our closed formula:

\ begin {ecuación*} a_n = 2\ cdot 3^n - 1. \ end {ecuación*}

La iteración puede ser desordenada, pero cuando la relación de recurrencia solo se refiere a un término anterior (y tal vez alguna función de\(n\)) puede funcionar bien. Sin embargo, tratar de iterar una relación de recurrencia tal como\(a_n = 2 a_{n-1} + 3 a_{n-2}\) será demasiado complicado. Habría que hacer un seguimiento de dos conjuntos de términos anteriores, cada uno de los cuales se expresaba en dos términos anteriores, y así sucesivamente. La longitud de la fórmula crecería exponencialmente (el doble cada vez, de hecho). Por suerte sucede que hay un método para resolver las relaciones de recurrencia que funciona muy bien en relaciones como esta.

La Técnica de Raíz Característica

Supongamos que queremos resolver una relación de recurrencia expresada como una combinación de los dos términos anteriores, como\(a_n = a_{n-1} + 6a_{n-2}\text{.}\) en otras palabras, queremos encontrar una función de la\(n\) que satisfaga\(a_n - a_{n-1} - 6a_{n-2} = 0\text{.}\) Ahora la iteración es demasiado complicada, pero piensa solo por un segundo lo que pasaría si lo hiciéramos iterar. En cada paso, multiplicaríamos, entre otras cosas, una iteración previa por 6. Entonces nuestra fórmula cerrada incluiría\(6\) multiplicado alguna cantidad de veces. Por lo tanto, es razonable adivinar que la solución contendrá partes que se vean geométricas. Quizás la solución tome la forma\(r^n\) para alguna constante\(r\text{.}\)

Lo bueno es que sabemos comprobar si una fórmula es realmente una solución a una relación de recurrencia: enchufarla. ¿Qué pasa si nos conectamos\(r^n\) a la recursión anterior? Obtenemos

\ begin {ecuación*} r^n - r^ {n-1} - 6r^ {n-2} = 0. \ end {ecuación*}

Ahora soluciona para\(r\text{:}\)

\ begin {ecuación*} r^ {n-2} (r^2 - r - 6) = 0,\ end {ecuación*}

así por factorización,\(r = -2\) o\(r = 3\) (o\(r = 0\text{,}\) aunque esto no nos ayude). Esto nos dice que\(a_n = (-2)^n\) es una solución a la relación de recurrencia, como es ¿\(a_n = 3^n\text{.}\)Cuál es la correcta? Ambos lo son, a menos que especifiquemos condiciones iniciales. Observe que también podríamos tener\(a_n = (-2)^n + 3^n\text{.}\) O\(a_n = 7(-2)^n + 4\cdot 3^n\text{.}\) De hecho, para cualquiera\(a\) y\(b\text{,}\)\(a_n = a(-2)^n + b 3^n\) es una solución (intente enchufar esto a la relación de recurrencia). Para encontrar los valores de\(a\) y\(b\text{,}\) utilizar las condiciones iniciales.

Esto nos apunta en la dirección de una técnica más general para resolver las relaciones de recurrencia. Observe que siempre seremos capaces de facturar\(r^{n-2}\) lo que hicimos anteriormente. Entonces realmente solo nos importa la otra parte. Llamamos a esta otra parte la ecuación característica para la relación de recurrencia. Nos interesa encontrar las raíces de la ecuación característica, que se llaman (sorpresa) las raíces características.

Raíces características

Dada una relación de recurrencia,\(a_n + \alpha a_{n-1} + \beta a_{n-2} = 0\text{,}\) el polinomio característico es

\ comenzar {ecuación*} x^2 +\ alfa x +\ beta\ fin {ecuación*}

dando la ecuación característica:

\ begin {ecuación*} x^2 +\ alfa x +\ beta = 0. \ end {ecuación*}

Si\(r_1\) y\(r_2\) son dos raíces distintas del polinomio característico (es decir, soluciones a la ecuación característica), entonces la solución a la relación de recurrencia es

\ begin {ecuación*} a_n = ar_1^n + br_2^n,\ end {ecuación*}

donde\(a\) y\(b\) son constantes determinadas por las condiciones iniciales.

Ejemplo\(\PageIndex{6}\)

Resolver la relación de recurrencia\(a_n = 7a_{n-1} - 10 a_{n-2}\) con\(a_0 = 2\) y\(a_1 = 3\text{.}\)

Solución

Reescribir la relación de recurrencia\(a_n - 7a_{n-1} + 10a_{n-2} = 0\text{.}\) Now form the characteristic equation:

\ begin {ecuación*} x^2 - 7x + 10 = 0\ end {ecuación*}

y resolver para\(x\text{:}\)

\ start {ecuación*} (x - 2) (x - 5) = 0\ end {ecuación*}

por lo\(x = 2\) and \(x = 5\) are the characteristic roots. We therefore know that the solution to the recurrence relation will have the form

\ start {ecuación*} a_n = a 2^n + b 5^n.\ end {ecuación*}

Para encontrar\(a\) and \(b\text{,}\) plug in \(n =0\) and \(n = 1\) to get a system of two equations with two unknowns:

\ begin {alinear*} 2\ amp = a 2^0 + b 5^0 = a + b\\ 3\ amp = a 2^1 + b 5^1 = 2a + 5b\ end {align*}

Resolver este sistema da\(a = \frac{7}{3}\) and \(b = -\frac{1}{3}\) so the solution to the recurrence relation is

\ begin {ecuación*} a_n =\ frac {7} {3} 2^n -\ frac {1} {3} 5^n.\ end {ecuación*}

Quizás la relación de recurrencia más famosa es la\(F_n = F_{n-1} + F_{n-2}\text{,}\) que junto con las condiciones iniciales\(F_0 = 0\) y\(F_1= 1\) define la secuencia de Fibonacci. Pero fíjense que este es precisamente el tipo de relación de recurrencia sobre la que podemos utilizar la técnica de raíz característica. Cuando lo haces, lo único que cambia es que la ecuación característica no factoriza, por lo que necesitas usar la fórmula cuadrática para encontrar las raíces características. De hecho, hacerlo da el tercer número irracional más famoso,\(\varphi\text{,}\) la proporción áurea.

Antes de dejar la técnica de raíz característica, debemos pensar en lo que podría suceder cuando resuelvas la ecuación característica. Tenemos un ejemplo anterior en el que el polinomio característico tiene dos raíces distintas. Estas raíces pueden ser números enteros, o quizás números irracionales (requiriendo la fórmula cuadrática para encontrarlos). En estos casos, sabemos cómo es la solución a la relación de recurrencia.

Sin embargo, es posible que el polinomio característico solo tenga una raíz. Esto puede suceder si los factores polinomiales característicos como\((x - r)^2\text{.}\) sigue siendo el caso que\(r^n\) sería una solución a la relación de recurrencia, pero no podremos encontrar soluciones para todas las condiciones iniciales usando la forma general\(a_n = ar_1^n + br_2^n\text{,}\) ya que no podemos distinguir entre\(r_1^n\) y \(r_2^n\text{.}\)Sin embargo, estamos de suerte:

Técnica de Raíz Característica para Raíces Repetidas

Supongamos que la relación de recurrencia\(a_n = \alpha a_{n-1} + \beta a_{n-2}\) tiene un polinomio característico con una sola raíz\(r\text{.}\) Entonces la solución a la relación de recurrencia es

\ begin {ecuación*} a_n = ar^n + bnr^n\ end {ecuación*}

donde\(a\) y\(b\) son constantes determinadas por las condiciones iniciales.

Observe el extra\(n\) en\(bnr^n\text{.}\) Esto nos permite resolver para las constantes\(a\) y a\(b\) partir de las condiciones iniciales.

Ejemplo\(\PageIndex{7}\)

Resolver la relación de recurrencia\(a_n = 6a_{n-1} - 9a_{n-2}\) con condiciones iniciales\(a_0 = 1\) y\(a_1 = 4\text{.}\)

Contestar

El polinomio característico es\(x^2 - 6x + 9\text{.}\) We solve the characteristic equation

\ begin {ecuación*} x^2 - 6x + 9 = 0\ end {ecuación*}

por factorización:

\ begin {ecuación*} (x - 3) ^2 = 0\ end {ecuación*}

por lo\(x =3\) is the only characteristic root. Therefore we know that the solution to the recurrence relation has the form

\ begin {ecuación*} a_n = a 3^n + bn3^n\ end {ecuación*}

para algunas constantes\(a\) and \(b\text{.}\) Now use the initial conditions:

\ begin {align*} a_0 = 1\ amp = a 3^0 + b\ cdot 0\ cdot 3^0 = a\\ a_1 = 4\ amp = a\ cdot 3 + b\ cdot 1\ cdot3 = 3a + 3b. \ end {alinear*}

Desde\(a = 1\text{,}\) we find that \(b = \frac{1}{3}\text{.}\) Therefore the solution to the recurrence relation is

\ begin {ecuación*} a_n = 3^n +\ frac {1} {3} n3^n.\ end {ecuación*}

Aunque no consideraremos ejemplos más complicados que estos, esta técnica de raíz característica se puede aplicar a relaciones de recurrencia mucho más complicadas. Por ejemplo,\(a_n = 2a_{n-1} + a_{n-2} - 3a_{n-3}\) tiene polinomio característico\(x^3 - 2 x^2 - x + 3\text{.}\) Suponiendo que veas cómo factorizar tal polinomio de grado 3 (o más) puedes encontrar fácilmente las raíces características y como tal resolver la relación de recurrencia (la solución se vería como\(a_n = ar_1^n + br_2^n + cr_3^n\) si hubiera 3 raíces distintas). También es posible resolver relaciones de recurrencia de la forma\(a_n = \alpha a_{n-1} + \beta a_{n-2} + C\) para alguna constante\(C\text{.}\) También es posible (y aceptable) que las raíces características sean números complejos.