Soy auto-estudio de funciones de generación (utilizando GeneratingFunctionology como un texto). Me encontré con este problema de programación, que me reconoció de inmediato como una modificación de la secuencia de Fibonacci. Yo quería poner mi recién encontrado la generación de la función de las técnicas a trabajar, así que trató de resolver la recurrencia.
El problema básicamente se reduce a resolver:
$$a_{n+2} = a_{n+1} + ka_n$$ Donde $n \ge 0$, e $k$ es algún entero positivo. Y, $a_0 = 1$, $a_1 = 1$.
Sin embargo, mi solución (abajo, pero no muy simplificado, ya que yo soy sólo conectarlo a un ordenador) los rendimientos de los valores que demasiado grande por un factor de $k$.
Mi solución:
$$a_n = \frac{r_2^{n+1} - r_1^{n+1}}{(r_2-r_1)r_1^{n+1}r_2^{n+1}}$$ Donde: $$r_1 = \frac{-1 - \sqrt{1+4k}}{2k}$$ $$r_2 = \frac{-1 + \sqrt{1+4k}}{2k}$$
Si alguien me podría ayudar a entender dónde me salió mal, me gustaría mucho aprecio. (No veo por qué no estoy demasiado grandes por un factor de $k$.)
Mi trabajo es la siguiente:
$$a_{n+2} = a_{n+1} + ka_n$$ $$\sum_{n\ge0}a_{n+2}x^n = \sum_{n\ge0}a_{n+1}x^n + k\sum_{n\ge0}a_{n}x^n$$
Deje $A(x) = \sum_{n\ge0}a_nx^n$. Entonces:
$$\frac{A(x) - a_0 - xa_1}{x^2} = \frac{A(x) - a_0}{x} + kA(x)$$ $$A(x)\left(\frac{1}{x^2} -\frac{1}{x} - k\right) = \frac{1+x}{x^2} - \frac{1}{x}$$ $$A(x)\left(\frac{1 - x - kx^2}{x^2}\right) = \frac{1}{x^2}$$ $$A(x)= \frac{1}{1 - x - kx^2}$$
Ahora, factorizando el denominador de los rendimientos de dos raíces, $r_1$ $r_2$ como se indica más arriba. Esto, a su vez, se obtiene: $$A(x) = \frac{1}{(x-r_1)(x-r_2)}$$ Parcial de las fracciones: $$A(x) = \frac{1}{r_2-r_1}\frac{1}{(r_1 - x)} - \frac{1}{r_2-r_1}\frac{1}{(r_2 - x)}$$ $$A(x) = \frac{1}{(r_2-r_1)(r_1)}\frac{1}{(1 - \frac{x}{r_1})} - \frac{1}{(r_2-r_1)(r_2)}\frac{1}{(1 - \frac{x}{r_2})}$$ $$A(x) = \frac{1}{(r_2-r_1)(r_1)}\sum_{n\ge0}{\left(\frac{x}{r_1}\right)^n} - \frac{1}{(r_2-r_1)(r_2)}\sum_{n\ge0}{\left(\frac{x}{r_2}\right)^n}$$
La combinación de: $$A(x) = \sum_{n\ge0} x^n \left(\frac{1}{(r_2-r_1)(r_1^{n+1})} - \frac{1}{(r_2-r_1)(r_2^{n+1})}\right)$$ Por lo tanto: $$a_n = \frac{r_2^{n+1} - r_1^{n+1}}{(r_2-r_1)r_1^{n+1}r_2^{n+1}}$$
