I have the following recurrence relation: $$a_n=F_0a_{n-1}+F_1a_{n-2}+F_2a_{n-3}...+F_{n-1}a_0 $$ with $a_0=5$ and $F_n$ being the nth Fibonacci number. How would I find the closed form of the generating function of this? The Fibonacci sequence is really confusing me here, and I'm not sure where to start.
Let $$f(x)=\sum_{n\geq 0}a_n\, x^n. \tag{1}$$ Since: $$g(x)=\sum_{n\geq 0}F_n\,x^n = \frac{x}{1-x-x^2}\tag{2}$$ and, for every $n\geq 1$: $$ [x^n](f(x))=a_n=F_0 a_{n-1}+\ldots F_{n-1} a_0 = [x^{n-1}]\left(f(x)\cdot g(x)\right)\tag{3}$$ we have (by multiplying both sides of the previous line by $x^{n-1}$ and summing over $n\geq 1$): $$ \frac{f(x)-5}{x}=f(x)\cdot g(x)\tag{4}$$ from which it follows that:
$$ f(x) = 5\cdot\frac{1-x-x^2}{1-x-2x^2}.\tag{5}$$
-
$\begingroup$ Is f(x) in the third line meant to be f(z)? I'm not sure where it comes from. $\endgroup$ – user234569 Apr 27 '15 at 11:51
-
$\begingroup$ @user234569: they are just mute variables. Anyway, now everything depends on $x$ only. $\endgroup$ – Jack D'Aurizio Apr 27 '15 at 11:55