En la función generadora de los números de Fibonacci

Question

Definamos los números de Fibonacci como $F_0=1$, $F_1=1$ y $F_n=F_{n-1}+F_{n-2}$. Usando esta recurrencia pude calcular la función generatriz de los números de Fibonacci como $-\frac{1}{x^2+x-1}$. Ahora, se puede demostrar que $F_n$ cuenta la lista de $1,2$ con suma $n$. ¿Hay alguna forma de encontrar la función generatriz usando este modelo sin usar la recurrencia?

Answer 1

El coeficiente de $x^k$ en $(x+x^2)^n$ da el número de formas de alcanzar un total de $k$ con $n$ términos, cada uno de los cuales es $1$ o $2$, por lo que el coeficiente de $x^k$ en $\sum_{n\ge 0}(x+x^2)^n$ da el número de formas de alcanzar un total de $k$ con cualquier número de términos, cada uno de los cuales es $1$ o $2. Pero formalmente$$\sum_{n\ge 0}(x+x^2)^n = \frac{1}{1-(x+x^2)} = \frac{1}{1-x-x^2},$$ que es tu función generadora.