¿Resolver una recursión utilizando funciones generadoras?

Question

Dada la ecuación recursiva :

$$F_n+F_{n-1}++F_0=3^n , n\geq0$$

Una solución rápida que se me ocurre es colocar $n-1$ en lugar de $n$ , y entonces obtendremos :

$$F_{n-1}+F_{n-2}++F_0=3^{n-1} $$

Ahora restando ambas ecuaciones :

$$F_n+F_{n-1}++F_0 - (F_{n-1}+F_{n-2}++F_0) = 3^n - 3^{n-1} $$

$$ F_n = 3^n - 3^{n-1}$$

¿Pero cómo puedo hacerlo utilizando funciones generadoras? ¿Alguna pista?

Gracias

Answer 1

Defina $f(z):=\sum F_n z^n$ y $g(z):=\sum z^n=\frac{1}{1-z}$ . Puede ver $\sum_{k=0}^{n}F_k$ como coeficiente de $f(z)g(z)$ dans le $n$ -término. Así obtenemos $$f(z)g(z)=\sum_{k=0}^{\infty}3^nz^n.$$ De aquí obtenemos $f(x)=\frac{1-z}{1-3z}=\frac{1}{3}+\frac{2}{3}\frac{1}{1-3z}=1+\sum_{k=1}^{\infty}\frac{2}{3}3^kz^k$ . El coeficiente de esto es su F_n.

La forma de pensar sobre estas dos funciones $f$ y $g$ es escribir $$\sum_{k=0}^{n}F_k$$ como $$\sum_{k=0}^{n}F_{k}G_{n-k}$$ que es el coeficiente de un producto de dos series. En este caso necesitamos $G_k=1$ . Por ello, las dos funciones deben ser las $f$ y $g$ arriba.

Así que, sí, multiplica ambos lados por $z^n$ (o $z^{-n}$ o a veces $z^n/n!$ ou $z^n/n$ depende de la recurrencia las funciones generadoras que van a ser útiles) suman para todo $n$ . A ambos lados se obtienen unas series. El truco es escribirlas en términos de funciones conocidas y $f(z)$ . Hay algunas operaciones conocidas sobre series que tienen fácil traducción en operaciones sobre la función. Ver aquí .

También hay un sitio muy bueno y gratuito (!) Libro .