Utilizar las funciones generadoras para resolver la ecuación de recurrencia.

Question

Dejemos que $a_0=1, a_1=1$ . Utilizar las funciones generadoras para resolver la ecuación de recurrencia $a_{n+2}= a_{n+1} + 2a_n$ para $n \geq0$

No tengo ni idea de cómo solucionarlo, se agradece cualquier ayuda.

Answer 1

El método de generación de funciones asocia a su secuencia la serie de potencias (formal) $$f(x)=\sum_{n=0}^\infty a_n x^n.$$ Tenga en cuenta que $\displaystyle\frac{f(x)-a_0}x=\sum_{n=0}^\infty a_{n+1}x^n$ Así que en el caso que nos ocupa, $$2f(x)+\frac{f(x)-a_0}x=\sum_{n=0}^\infty (2a_n+a_{n+1})x^n=\sum_{n=0}^\infty a_{n+2}x^n=\frac{f(x)-a_0-a_1x}{x^2}.$$ Esto significa que $$2x^2f(x)+xf(x)-a_0x=f(x)-a_0-a_1x.$$ Desde $a_0=a_1=1$ esto se simplifica a $$f(x)=\frac1{1-x-2x^2}.$$ La cuestión es que podemos encontrar la serie de potencias asociada a esta función y, por tanto, obtener una fórmula para la $a_n$ . En este caso, utilizando el método de las fracciones parciales, encontramos que $$f(x)=\frac{\frac13}{1-(-x)}+\frac{\frac23}{1-2x},$$ y podemos ampliarlo utilizando $\displaystyle\sum_{n=0}^\infty (rx)^n=\frac1{1-rx}$ para cualquier $r$ . Obtenemos $$f(x)=\frac13\sum_{n=0}^\infty(-x)^n+\frac23\sum_{n=0}^\infty(2x)^n=\sum_{n=0}^\infty\left(\frac{(-1)^n+2^{n+1}}3\right)x^n,$$ así que $$a_n=\frac{(-1)^n+2^{n+1}}3.$$ (Naturalmente, puedes comprobar que esto funciona, ya que la fórmula te da que $a_0=a_1=1$ y $a_{n+2}=a_{n+1}+2a_n$ .)

Algunos comentarios: La manipulación es puramente formal, es decir, no hay que preocuparse por establecer que las series convergen en algún intervalo. En este caso sí lo hacen, pero se puede operar de forma puramente algebraica sin preocuparse por ello. Una buena referencia introductoria para estas cuestiones es Series formales de potencia de Ivan Niven, ganador del premio Lester R. Ford de 1970 a la mejor exposición.

Observa que el denominador de la función racional que hemos obtenido es $1-x-2x^2$ . Si $a_{n+2}=\alpha a_{n+1}+\beta a_n$ el denominador habría sido $1-\alpha x-\beta x^2$ . El numerador en este caso era $1$ . Si $a_{n+2}=\alpha a_{n+1}+\beta a_n$ , habría sido $a_0+(a_1-a_0\alpha)x$ . De ello se deduce que la fórmula general de $a_n$ tiene la forma $Ar^n+Bs^n$ donde $r\ne s$ son las raíces de la cuadrática $1-\alpha x-\beta x^2$ y $A,B$ son algunas constantes. Si la cuadrática tiene raíces repetidas (es decir, si $r=s$ ), esto cambia ligeramente a $(A+Bn)r^n$ . Resultados similares son válidos para las recurrencias con más términos.

Son posibles otros enfoques (formales). Por ejemplo, podríamos considerar en su lugar el exponencial generando series, $$f(x)=\sum_{n=0}^\infty \frac{a_n}{n!}x^n.$$ En este caso, tenemos $$f'(x)=\sum_{n=0}^\infty\frac{a_{n+1}}{n!}x^n$$ y $$f''(x)=\sum_{n=0}^\infty\frac{a_{n+2}}{n!}x^n,$$ e identificando $f$ se convierte ahora en una cuestión de resolver una ecuación diferencial lineal. Ahora $f$ es una combinación lineal de exponenciales $e^{rx}$ y $e^{sx}$ con $r,s$ como antes.

Otro enfoque utiliza el álgebra lineal: Hay una matriz $A$ (con coeficientes constantes) que transforma $(a_n\, a_{n+1})^T$ en $(a_{n+1}\, a_{n+2})^T$ . ( $T$ indica transposición). Los números $r,s$ corresponden ahora a las raíces del polinomio característico de $A$ . La fórmula del $a_n$ se obtiene a partir de una fórmula para $A^n$ que se puede obtener a partir de su forma canónica de Jordan.

Answer 2

Dejemos que $$g(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n+\cdots,$$ $$-xg(x)=-a_0x-a_1x^2-a_2x^3-\cdots-a_nx^{n+1}-\cdots,$$ $$-2x^2g(x)=-2a_0x^2-a_1x^3-a_2x^4-\cdots-a_nx^{n+2}-\cdots.$$ La suma de estas tres cantidades nos da $$(1-x-2x^2)g(x)=a_0+(a_1-a_0)x+(a_2-a_1-2a_0)x^2+\cdots.$$ Desde $a_0=1$ , $a_1=1$ , $a_2=3$ y así sucesivamente, vemos que $$(1-x-2x^2)g(x)=1$$ y así $$g(x)={1\over (1-x-2x^2)}={1\over (1+x)(1-2x)}.$$ Utilizando la descomposición parcial de la fracción tenemos $${1\over (1+x)(1-2x)}={A\over 1+x}+{B\over 1-2x}.$$ Así que la resolución de $A$ y $B$ obtenemos $A={1\over 3}$ y $B={2\over 3}$ . Esto nos da $${1\over 3}\cdot{1\over 1-(-x)}+{2\over 3}\cdot{1\over 1-2x}.$$ Utilizando la serie geométrica tenemos $${1\over 3}\sum_{n=0}^\infty(-1)^nx^n+{2\over 3}\sum_{n=0}^\infty(-2)^nx^n.$$ Así, $$a_n={1\over 3}(-1)^n+{2\over 3}(-2)^n.$$

Answer 3

El método de uso de las funciones generadoras para resolver las relaciones de recurrencia se puede encontrar en el siguiente enlace.

http://faculty.tru.ca/smcguinness/M270F11/M270F11notes3.pdf

Mira algunos ejemplos y estoy seguro de que te darás cuenta rápidamente.