Let's define the Fibonacci numbers as $F_0=1$, $F_1=1$ and $F_n=F_{n-1}+F_{n-2}$. Using this recurrence I was able to calculate the generating function of the Fibonacci numbers to be $-\frac{1}{x^2+x-1}$. Now, it can be proved that $F_n$ counts the list of $1,2$ with sum $n$. Is there a way to find the generating function using this model without using the recurrence?
$\begingroup$ $\endgroup$
3 
1 Answer
$\begingroup$ $\endgroup$
The coefficient of $x^k$ in $(x+x^2)^n$ gives the number of ways to reach a total of $k$ with $n$ terms, each of which is $1$ or $2$, so the coefficient of $x^k$ in $\sum_{n\ge 0}(x+x^2)^n$ gives the number of ways to reach a total of $k$ with any number of terms, each of which is $1$ or $2$. But formally $$\sum_{n\ge 0}(x+x^2)^n = \frac{1}{1-(x+x^2)} = \frac{1}{1-x-x^2},$$ which is your generating function.
Using this recurrence I was able to calculate .... Could you please say more as to how you figured out this generating function based on F(0), F(1), and F(N)? $\endgroup$