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?

$\endgroup$
  • $\begingroup$ @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). $\endgroup$ – Brian M. Scott Oct 19 '11 at 4:18
  • $\begingroup$ @Brian: Oh, you're right, I wasn't reading closely enough. $\endgroup$ – anon Oct 19 '11 at 4:28
  • $\begingroup$ 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$ – Kevin Meredith Oct 29 '14 at 0:16
9
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.