3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How did you know the coefficient is $x^{n-1}$? $\endgroup$ – user235116 Apr 28 '15 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 '15 at 12:10
  • $\begingroup$ For the first line should it be $F_ka_{n-k-1}$ $\endgroup$ – user235116 Apr 28 '15 at 12:14
  • $\begingroup$ @user235116:No, I don't think so. $\endgroup$ – Martin R Apr 28 '15 at 12:21
  • $\begingroup$ Ok, thank you this help alot. $\endgroup$ – user235116 Apr 28 '15 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.