This is a given recurrence relation


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.


1 Answer 1


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.

  • $\begingroup$ How did you know the coefficient is $x^{n-1}$? $\endgroup$
    – user235116
    Apr 28, 2015 at 12:04
  • $\begingroup$ @user235116: It follows from the product formula for power series. I have expanded the answer, let me know if that helps. You can also "see" it if you expand the first terms of the product. $\endgroup$
    – Martin R
    Apr 28, 2015 at 12:10
  • $\begingroup$ For the first line should it be $F_ka_{n-k-1}$ $\endgroup$
    – user235116
    Apr 28, 2015 at 12:14
  • $\begingroup$ @user235116:No, I don't think so. $\endgroup$
    – Martin R
    Apr 28, 2015 at 12:21
  • $\begingroup$ Ok, thank you this help alot. $\endgroup$
    – user235116
    Apr 28, 2015 at 12:23

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.