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@anon: I believe that Alex is asking whether itβs possible to derive the generating function for the solution to the sum problem without first determining that the solution is the Fibonacci sequence (offset by one term). β 2011-10-19
-
0@Brian: Oh, you're right, I wasn't reading closely enough. β 2011-10-19
-
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.