2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$$

$\endgroup$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.