3
$\begingroup$

So I'm given the generating function $F(x)={1+2x\over1-3x^2}$ I'm supposed to find the recurrence relation satisfied by fn. I managed to get it into 2 separate geometric series and derive $f_n = {5(3^n)-(-3^n)\over6}$ but can't derive it in terms of past values of $f_n$. Help please, I have exam tomorrow!!!

EDIT: I just realised the $f_n$ I derived is wrong, ignore that.

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

$F(x)=\sum_{i\ge 0}a_ix^i$, where $a_0=1,a_1=2$ and $a_i=3a_{i-2}$ for $i\ge 2$.

$\endgroup$
4
  • 2
    $\begingroup$ Do you mind elaborating how you arrived at the answer? I have trouble expanding the function. $\endgroup$
    – huhehu
    Nov 10, 2013 at 9:30
  • 1
    $\begingroup$ @huhehu: I multiplied the left hand of $(1-3x^2)\sum_{i\ge 0}a_ix^i=i+2x$ and equated coefficients. $\endgroup$
    – Boris Novikov
    Nov 10, 2013 at 9:48
  • $\begingroup$ Ah yes, I found it! Cheers! $\endgroup$
    – huhehu
    Nov 10, 2013 at 9:57
  • $\begingroup$ @huhehu: It’s really just the reverse of the process that you use to derive a generating function from a recurrence. $\endgroup$
    – Brian M. Scott
    Nov 10, 2013 at 9:57

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.