# Non-homogeneous Recurrence Relation with Fibonacci Sequence

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?

• Yes I know, but the next question asks for an explicit form for $b_n$, that's where I'm having trouble. Apr 24 '16 at 8:38
• Your partial fraction does not seem to have a $z$ on top. Apr 24 '16 at 8:51
• 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. Apr 24 '16 at 10:13
• can someone explain that how to arrive at that generating function? Mar 11 '19 at 7:23

## 1 Answer

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

• Thank you so much! I feel so silly missing that bit about the z. Apr 25 '16 at 2:37