A non-homogeneous recurrence of Fibonacci sequence

Question

I am working on Fibonacci sequence (recursively) But the hack is that I have the following non-homogeneous version: $$F_n =F_{n-1} +F_{n-2} +g(n)$$ Where:

$F_1=g(1)$

$F_0=g(0)$

I have to use:

$$G(x)=\sum_0^\infty g(n) \times x^n$$

I cannot find the characteristic equation. I checked a couple of things on internet. Maybe I did not understand them or there would be a special version.

Thanks in advance community

Answer 1

As Robert Israel has pointed out the method is as follows.

For the difference equation $F_{n+2} = F_{n+1} + F_{n} + g(n+2)$ where $g(0) = F_{0}$, and $g(1) = F_{1}$ then \begin{align} \sum_{n=0}^{\infty} F_{n+2} \, t^{n} &= \sum_{n=0}^{\infty} F_{n+1} \, t^{n} + \sum_{n=0}^{\infty} F_{n} \, t^{n} + \sum_{n=0}^{\infty} g(n+2) \, t^{n} \\ \sum_{n=2} F_{n} \, t^{n-2} &= \sum_{n=1} F_{n} \, t^{n-1} + \sum_{n=0} F_{n} \, t^{n} + \sum_{n=2} g(n) \, t^{n-2} \\ \frac{1}{t^{2}} \left( -F_{0} - F_{1} t + \phi(t) \right) &= \frac{1}{t} \left( - F_{0} + \phi(t) \right) + \phi(t) + \frac{1}{t^{2}} \left( - g(0) - g(1) t + G(t) \right) \end{align} which leads to \begin{align} (1-t-t^{2}) \, \phi(t) = F_{0} - g(0) + (F_{1} - g(1)) t + G(t) \end{align} and finally \begin{align} \phi(t) = \frac{G(t)}{1- t- t^{2}} \end{align} where \begin{align} \phi(t) = \sum_{n=0}^{\infty} F_{n} \, t^{n} \hspace{10mm} G(t) = \sum_{n=0}^{\infty} g(n) \, t^{n}. \end{align}

Answer 2

1. Don't call this the "Fibonacci sequence" - it isn't.
2. Look at $f(x) = \sum_{n=0}^\infty F(n) x^n$. Use your recurrence to express this in terms of $G(x)$.