9.6: Usar funciones de generación para resolver recurrencias
- Page ID
- 118571
El enfoque que hemos visto hasta ahora en este capítulo no es la única manera de resolver ecuaciones de recurrencia. Adicionalmente, realmente solo se aplica a ecuaciones de recurrencia lineal con coeficientes constantes. En lo que resta del capítulo, veremos algunos ejemplos de cómo generar funciones se pueden utilizar como otra herramienta para resolver ecuaciones de recurrencia. En esta sección, nuestro enfoque estará en las ecuaciones de recurrencia lineal. En la Sección 9.7, veremos cómo generar funciones pueden resolver una recurrencia no lineal.
Nuestro primer ejemplo es la recurrencia homogénea que corresponde a la ecuación del operador de avance en el Ejemplo 9.9.
Considere la ecuación de recurrencia\(r_n+r_{n−1}−6r_{n−2}=0\) para la secuencia\(\{r_n:n \geq 0\}\) con\(r_0=1\) y\(r_1=3\). Esta secuencia tiene función generadora
\(f(x) = \displaystyle \sum_{n=0}^{\infty} r_nx^n = r_0 + r_1x + r_2x^2 + r_3x^3 + \cdot \cdot \cdot\).
Ahora considera por un momento cómo es\(xf(x)\) la función. Tiene\(r_{n−1}\) como coeficiente encendido\(x_n\). De igual manera, en la función\(−6x^2f(x)\), el coeficiente on\(x^n\) es\(−6r_{n−2}\).
¿Cuál es nuestro punto en todo esto? Bueno, si los sumamos todos, fíjense en lo que sucede. El coeficiente on\(x_n\) se convierte\(r_n+r_{n−1}−6r_{n−2}\), que es 0 por la ecuación de recurrencia! Ahora veamos cómo se alinea todo esto:
\(f(x) = r_0 + r_1x + r_2x^2 + r_3x^3 + \cdot \cdot \cdot + r_nx^n + \cdot \cdot \cdot\)
\(xf(x) = 0 + r_0x + r_1x^2 + r_2x^3 + \cdot \cdot \cdot r_{n-1}x^n + \cdot \cdot \cdot\)
\(-6x^2f(x) = 0 + 0 - 6r_0x^2 - 6r_1x^3 + \cdot \cdot \cdot -6r_{n-2}x^n + \cdot \cdot \cdot\)
Cuando agregamos el lado izquierdo, obtenemos\(f(x)(1+x−6x^2)\). En el lado derecho, el coeficiente on\(x^n\) for\(n \geq 2\) es 0 debido a la ecuación de recurrencia. Sin embargo, nos quedamos con\(r_0+(r_0+r_1)x=1+4x\), usando las condiciones iniciales. Así, tenemos la ecuación
\(f(x)(1+x−6x^2)=1+4x\),
o\(f(x)=(1+4x)/(1+x−6x^2)\). Esta es una función generadora que podemos atacar usando fracciones parciales en SameMath:
//Código
Esto nos demuestra que
\(f(x) = \dfrac{6}{5} \dfrac{1}{1-2x} - \dfrac{1}{5} \dfrac{1}{1+3x} = \dfrac{6}{5} \displaystyle \sum_{n=0}^{\infty} 2^nx^n - \dfrac{1}{5} \sum_{n=0}^{\infty}(-3)^nx^n\).
A partir de aquí, leemos\(r_n\) como el coeficiente encendido\(x^n\) y tenemos\(r_n = (6/5)2^n - (1/5)(-3)^n\).
Aunque hay un poco más de trabajo involucrado, este método también puede usarse para resolver ecuaciones de recurrencia no homogéneas, como ilustra el siguiente ejemplo.
La ecuación de recurrencia no\(r_n−r_{n−1}−2r_{n−2}=2^n\) es homogénea. Dejar\(r_0=2\) y\(r_1=1\). Esta vez, para resolver la recurrencia, comenzamos multiplicando ambas partes por\(x^n\). Esto da la ecuación
\(r_nx^n - r_{n-1}x^n - 2r_{n-2}x^n = 2^nx^n\).
Si sumamos esto sobre todos los valores de\(n \geq 2\), tenemos
\(\displaystyle \sum_{n=2}^{\infty} r_nx^n - \sum_{n=2}^{\infty} r_{n-1}x^n - 2\sum_{n=2}^{\infty} r_{n-2}x^n = \sum_{n=2}^{\infty} 2^nx^n\).
El lado derecho que debes reconocer fácilmente como casi igual a\(1/(1−2x)\). Nos falta el 1 y los\(2x\) términos, sin embargo, por lo que debemos restarlos de la forma de función racional de la serie. En el lado izquierdo, sin embargo, necesitamos hacer un poco más de trabajo.
A la primera suma sólo le faltan los dos primeros términos de la serie, así que podemos reemplazarla por\(R(x)−(2+x)\), dónde\(R(x)=\sum_{n=0}^{\infty} r_nx^n\). La segunda suma es casi\(xR(x)\), salvo que le falta el primer término. Por lo tanto, es igual a\(xR(x)−2x\). La suma en el término final es simplemente\(x^2R(x)\). Así, la ecuación puede ser reescrita como
\(R(x) - (2+x) - (xR(x) -2x) - 2x^2R(x) = \dfrac{1}{1-2x} - 1 -2x\).
Un poco de álgebra luego nos lleva a la función generadora
\(R(x) = \dfrac{6x^2 - 5x + 2}{(1-2x)(1-x-2x^2)}\).
Esta función generadora se puede expandir usando fracciones parciales en SameMath:
//Código
Por lo tanto, usando el Ejemplo 8.7 para la segunda función racional, tenemos
\(R(x) = - \dfrac{1}{9(1-2x)} + \dfrac{2}{3(1-2x)^2} + \dfrac{13}{9(1+x)}\)
\(= - \dfrac{1}{9} \displaystyle \sum_{n=0}^{\infty} 2^nx^n + \dfrac{2}{3} \sum_{n=0}^{\infty} \dbinom{n+2-1}{1} 2^nx^n + \dfrac{13}{9} \sum_{n=0}^{\infty} (-1)^nx^n\).
A partir de esta función generadora, podemos leer que
\(r_n = - \dfrac{1}{9} 2^n + \dfrac{2(n+1)}{3} 2^n + \dfrac{13}{9} (-1)^n = \dfrac{5}{9} 2^n + \dfrac{2}{3} n2^n + \dfrac{13}{9} (-1)^n\).
Las ecuaciones de recurrencia de los dos ejemplos de esta sección pueden resolverse utilizando las técnicas que estudiamos anteriormente en el capítulo. Un beneficio potencial para el enfoque de función generadora para ecuaciones no homogéneas es que no requiere determinar una forma apropiada para la solución particular. Sin embargo, el método de generación de funciones a menudo requiere que la función generadora resultante se expanda usando fracciones parciales. Ambos enfoques tienen aspectos positivos y negativos, por lo que a menos que se le indique que use un método específico, debe elegir el que le parezca más apropiado para una situación determinada. En la siguiente sección, veremos una ecuación de recurrencia que se resuelve más fácilmente usando funciones generadoras porque es no lineal.