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?
On the generating function of the Fibonacci numbers
6
$\begingroup$
sequences-and-series
recurrence-relations
generating-functions
fibonacci-numbers
-
0`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)? – 2014-10-29
1 Answers
9
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.