I have this question in my assignment, I'm just not sure how to handle finding the closed form fully. I have most of it. Here's the question for context.

Recall that the Fibonacci sequence is defined by the initial conditions $$F_0 = 0, F_1 = 1$$ and the recurrence relation $F_n = F_{n−1} + F_{n−2}, n >= 2.$ Consider the recurrence relation $b_n = 2b_{n−1} − b_{n−2} + F_n, n >= 2$ With $b_0 = 0, b_1 = 1.$ Derive a closed formula for the generating function B(z) of the sequence $b_n.$

I have my generating function, but I can't seem to find and explicit formula because of the last term. The actual generating function as I have it is: $$B(z)=\frac{z}{(1-z)^2(1-z-z^2)}$$ $$B(z)= 2 \sum_{n=0}^\infty F_nz^n -2\sum_{n=0}^\infty z^n-\sum_{n=0}^\infty (n+1)z^n +\frac{3}{1-z-z^2}$$ I'm not sure how to return the last bit into a series form since the Fibonacci generating function has the z on top. The explicit form also wouldn't have the Fibonacci sequence in it would it?

  • $\begingroup$ Yes I know, but the next question asks for an explicit form for $b_n$, that's where I'm having trouble. $\endgroup$
    – Nico Monk
    Apr 24 '16 at 8:38
  • $\begingroup$ Your partial fraction does not seem to have a $z$ on top. $\endgroup$
    – almagest
    Apr 24 '16 at 8:51
  • $\begingroup$ I split the closed form into $B(z)= \frac{2z+3}{1-z-z^2} - \frac{2}{1-z} -\frac{1}{(1-z)^2}$. Then I split those fractions into their respective series. $\endgroup$
    – Nico Monk
    Apr 24 '16 at 10:13
  • $\begingroup$ can someone explain that how to arrive at that generating function? $\endgroup$
    Mar 11 '19 at 7:23

You have $\frac{z}{1-z-z^2}=F_1z+F_2z^2+F_3z^3+\dots$, so $\frac{1}{1-z-z^2}=F_1+F_2z+F_3z^2+\dots+F_{n+1}z^n+\dots$.

So that gives $b_n=-2-(n+1)+3F_{n+1}+2F_n=F_{n+4}-(n+3)$

  • $\begingroup$ Thank you so much! I feel so silly missing that bit about the z. $\endgroup$
    – Nico Monk
    Apr 25 '16 at 2:37

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.