# Derive a closed formula for the generating function of this recurrence relation

This is a given recurrence relation

$a_n=19(F_0a_{n-1}+F_1a_{n-2}+...+F_{n-1}a_0)$

where $F_n$ is Fibonacci number and $a_0=9$. Find the generating function $A(x)$ of the sequence $a_n$

I get the generating function for $F_n=\frac x{1-x-x^2}$

I try this for hour with derivative method $A'(x)$ but I still do not get it. Can you help me please, any method is fine.

From $$F(x)A(x) = \sum_{n=0}^\infty F_nx^n \cdot \sum_{n=0}^\infty a_nx^n = \sum_{n=0}^\infty \Bigl( \sum_{k=0}^n F_k a_{n-k}\Bigr) x^n$$
we see that $F_0a_{n-1}+F_1a_{n-2}+...+F_{n-1}a_0$ is the coefficient of $x^{n-1}$ in $F(x)A(x)\,$, or the coefficient of $x^n$ in $xF(x)A(x)\,$.
Therefore your recurrence relation can be expressed in terms of the generating functions as $$A(x) = 9 + 19 \, x \, A(x) F(x)$$ and $F(x)$ is known.
• How did you know the coefficient is $x^{n-1}$? Apr 28 '15 at 12:04
• For the first line should it be $F_ka_{n-k-1}$ Apr 28 '15 at 12:14