A non-homogeneous recurrence of Fibonacci sequence 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
 A: *

*Don't call this the "Fibonacci sequence" - it isn't.

*Look at $f(x) = \sum_{n=0}^\infty F(n) x^n$.  Use your recurrence to express this in terms of $G(x)$.

A: 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}
