Una recurrencia no homogénea de la secuencia de Fibonacci

Question

Estoy trabajando en la secuencia de Fibonacci (recursivamente) Pero el hack es que tengo la siguiente versión no homogénea: $$F_n =F_{n-1} +F_{n-2} +g(n)$$ Dónde:

$F_1=g(1)$

$F_0=g(0)$

Tengo que usar:

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

No puedo encontrar la ecuación característica. He consultado un par de cosas en Internet. Tal vez no los entendí o habría una versión especial.

Gracias de antemano comunidad

Answer 1

1. No llame a esto la "secuencia de Fibonacci" - no lo es.
2. Mira $f(x) = \sum_{n=0}^\infty F(n) x^n$ . Utilice su recurrencia para expresar esto en términos de $G(x)$ .

Answer 2

Como ha señalado Robert Israel, el método es el siguiente.

Para la ecuación de diferencia $F_{n+2} = F_{n+1} + F_{n} + g(n+2)$ donde $g(0) = F_{0}$ y $g(1) = F_{1}$ entonces \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} lo que lleva a \begin{align} (1-t-t^{2}) \, \phi(t) = F_{0} - g(0) + (F_{1} - g(1)) t + G(t) \end{align} y finalmente \begin{align} \phi(t) = \frac{G(t)}{1- t- t^{2}} \end{align} donde \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}