6
$\begingroup$

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?

  • 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 1

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.