3.5: Relaciones de recurrencia
- Page ID
- 117082
Una relación de recurrencia define una secuencia\(\{a_i\}_{i=0}^\infty\) expresando un término típico\(a_n\) en términos de términos anteriores,\(a_i\) para\(i< n\). Por ejemplo, la famosa secuencia de Fibonacci se define por
\[ F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}.\nonumber \]
Tenga en cuenta que se deben especificar algunos valores iniciales para que la relación de recurrencia defina una secuencia única.
El índice de inicio para la secuencia no necesita ser cero si no tiene sentido o algún otro índice de inicio es más conveniente. Vimos dos relaciones de recurrencia para el número de desórdenes de\([n]\):
\[D_1=0, D_n=nD_{n-1}+(-1)^n.\nonumber \]
y
\[D_1=0, D_2=1, D_n=(n-1)(D_{n-1}+D_{n-2}).\nonumber \]
“Resolver” una relación de recurrencia significa encontrar una fórmula para\(a_n\). Existen diversos métodos para resolver las relaciones de recurrencia, con diversas ventajas y desventajas en casos particulares. Un método que funciona para algunas relaciones de recurrencia implica generar funciones. La idea es sencilla, si la ejecución no siempre es: Vamos
\[f(x)=\sum_{i=0}^\infty a_ix^i,\nonumber \]
es decir, que\(f(x)\) sea la función generadora para\(\{a_i\}_{i=0}^\infty\). Ahora tratamos de manipular\(f(x)\), usando la relación de recurrencia, hasta que podamos resolver para\(f(x)\) explícitamente. Por último, esperamos que podamos encontrar una fórmula para los coeficientes a partir de la fórmula para\(f(x)\).
Ejemplo\(\PageIndex{1}\)
Resolver\(F_0=0\)\( F_1=1\),,\( F_n=F_{n-1}+F_{n-2}\).
Solución
Vamos\[f(x)=\sum_{i=0}^\infty F_ix^i\nonumber \]
y tenga en cuenta que
\[xf(x)=\sum_{i=0}^\infty F_ix^{i+1}=\sum_{i=1}^\infty F_{i-1}x^{i}.\nonumber \]
Para obtener la segunda suma simplemente hemos “reindexado” para que el valor del índice dé el exponente encendido\(x\), al igual que en la serie para\(f(x)\). Asimismo,
\[x^2f(x)=\sum_{i=0}^\infty F_ix^{i+2}=\sum_{i=2}^\infty F_{i-2}x^{i}.\nonumber \]
En una forma algo más sugerente, tenemos
\[\matrix{ f(x)&=&x&+&F_2x^2&+&F_3x^3&+&F_4x^4&+\cdots\cr xf(x)&=&&&x^2&+&F_2x^3&+&F_3x^4&+\cdots\cr x^2f(x)&=&&&&&x^3&+&F_2x^4&+\cdots\cr}\nonumber \]
y combinando las tres ecuaciones que obtenemos
\[f(x)-xf(x)-x^2f(x)=x + (F_2-1)x^2+(F_3-F_2-1)x^3+(F_4-F_3-F_2)x^4+\cdots\nonumber \]
o en forma más compacta
\[\eqalign{ f(x)-xf(x)-x^2f(x) &=\sum_{i=0}^\infty F_ix^i - \sum_{i=1}^\infty F_{i-1}x^{i} - \sum_{i=2}^\infty F_{i-2}x^{i}\cr &=x+\sum_{i=2}^\infty (F_i-F_{i-1}-F_{i-2})x^i\cr &=x+\sum_{i=2}^\infty 0\cdot x^i\cr &=x,\cr }\nonumber \]
recordando que\(F_0=0\) y\(F_1=1\). Ahora
\[f(x)={x\over 1-x-x^2}={-x\over x^2+x-1}.\nonumber \]
Si podemos encontrar una representación explícita para la serie para esta función, habremos resuelto la relación de recurrencia. Aquí es donde las cosas podrían salir mal, pero en este caso funciona. Dejar\(a\) y\(b\) ser las raíces de\(x^2+x-1\); usando la fórmula cuadrática, obtenemos\[a={-1+\sqrt5\over2}, b={-1-\sqrt5\over2}.\nonumber\] Prestando una técnica del cálculo, escribimos
\[{-x\over x^2+x-1}={A\over x-a}+{B\over x-b}.\nonumber \]
Resolviendo\(A\) y\(B\) da
\[A={1-\sqrt5\over2\sqrt5}, B={-1-\sqrt5\over 2\sqrt5}.\nonumber \]
Entonces
\[{-x\over x^2+x-1}=-{A\over a}{1\over 1-x/a}-{B\over b}{1\over 1-x/b}.\nonumber \]
A partir del cálculo sabemos que
\[{1\over 1-x/a}=\sum_{i=0}^\infty (1/a)^ix^i\quad\hbox{and}\quad {1\over 1-x/b}=\sum_{i=0}^\infty (1/b)^ix^i.\nonumber \]
Finalmente, esto significa que el coeficiente de\(x^i\) en la serie para\(f(x)\) es
\[F_i=-{A\over a}(1/a)^i-{B\over b}(1/b)^i.\nonumber \]
Simplificando da
\[F_i={1\over\sqrt5}\Bigl({1+\sqrt5\over2}\Bigr)^i- {1\over\sqrt5}\Bigl({1-\sqrt5\over2}\Bigr)^i.\nonumber \]
Sage puede resolver muchas relaciones de recurrencia; esto nos permite verificar nuestras respuestas. A veces el formato puede ser un poco diferente al que obtienes a mano.
from sympy import Function, rsolve
from sympy.abc import n
y = Function('y')
g = y(n)-y(n-1)-y(n-2)
rsolve(g, y(n), { y(0):0, y(1):1 })
He aquí una característica interesante de esta expresión: ya que\(|(1-\sqrt5)/2|< 1\), el límite de\(((1-\sqrt5)/2)^i\) como\(i\) va al infinito es 0. Entonces, cuando\(i\) es grande,
\[F_i=\mathop{\hbox{round}} \left({1\over\sqrt5}\Bigl({1+\sqrt5\over2}\Bigr)^i\right),\nonumber \]
es decir, el primer término redondeado al entero más cercano. Resulta que esto es cierto empezando por\(i=0\).
Podemos checar esto en Sage.
f(x)=((1+sqrt(5))/2)^x/sqrt(5) [round(N(f(i))) for i in range(0,21)]
Puedes ver cómo hacer la solución completa en Sage.
También podemos usar esta expresión\(F_n\) para calcular\(\lim_{n\to\infty}F_n /F_{n-1}\).
\[\underset{n\to\infty}{\lim}\frac{F_{n}}{F_{n-1}}=\underset{n\to\infty}{\lim}\frac{\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n -\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n}{\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}}=\frac{1+\sqrt{5}}{2}. \nonumber\]
Esta es la llamada “proporción áurea”.