Preguntas del libro de texto sobre la generación de funciones

Question

Hago matemáticas haciendo problemas de práctica en mi libro de texto.

Pude encontrar la fórmula explícita para $a_n$ tal que $a_{n+1}=a_n+2^n$ (que es $2^k-1$ ) Entiendo los teoremas, pero tengo problemas para resolver las preguntas.

Ya estoy atascado en el segundo problema. ¿Cómo puedo encontrar la fórmula explícita para la secuencia $a_n$ que se define por la relación de recurrencia $a_{n+2}=a_{n+1}+2a_n$ y $a_0=a_1=1$ ? En primer lugar, ¿cómo puedo encontrar una función generadora?

Answer 1

Digamos que tenemos una función generadora $g(x) = \displaystyle \sum_{n=0}^\infty a_n x^n$ para $a_n$ .

Entonces $g(x) = \displaystyle 1 + x + \sum_{n=2}^\infty (a_{n-1} + 2a_{n-2})x^n = 1 + x + \sum_{n=2}^\infty a_{n-1}x^n + 2\sum_{n=2}^\infty a_{n-2}x^n$

Pero tenemos que $\displaystyle \sum_{n=2}^\infty a_{n-1}x^n = x \sum_{n=2}^\infty a_{n-1} x^{n-1} = x(g(x) - 1)$ y de forma similar, $\displaystyle \sum_{n=2}^\infty a_{n-2}x^n = x^2 \sum_{n=2}^\infty a_{n-2}x^{n-2} = x^2g(x)$ .

Esto significa que $g(x) = 1 + x + x(g(x) - 1) + 2x^2g(x)$ . A partir de ahí puedes resolver la función generadora y trabajar en la extracción de los coeficientes.

Answer 2

Dejemos que $F(x)$ sea $\sum_{n=0}^{\infty}a_nx^n$ la función generadora.

Para encontrar el $F(x)$ En este caso, la relación de recurrencia de los términos se convierte en una ecuación que involucra a la función generadora, así: $$a_{n+2} = a_{n+1} + 2a_n$$ $$\sum_{n=0}^{\infty}a_{n+2}x^n = \sum_{n=0}^{\infty}a_{n+1}x^n + 2\sum_{n=0}^{\infty}a_nx^n$$ Ahora, como, por ejemplo, $\sum_{n=0}^{\infty}a_{n+1}x^n = \frac{F(x)-a_0}{x}$ podemos escribirlo como $$\frac{F(x)-a_0-a_1x}{x^2} = \frac{F(x)-a_0}{x} + 2F(x),$$ que, tras un poco de álgebra, puede resolverse para $F(x)$ .

Para encontrar la fórmula explícita, se puede tomar la función racional que se obtiene para $F(x)$ y expandirla en una serie de potencias utilizando fracciones parciales. La fórmula resultante puede ser bastante complicada, e implica raíces de polinomios en la función generadora.