Sure thing, there's nothing to it, really.
Step 1. Define the generating function
 = \sum_{n=0}^\infty f_n x^n)
where
is the nth Fibonacci number. F is our clothesline upon which we hang up our sequence of numbers for display!
Step 2. Write down the recurrence equation,
and multiply it by
, then sum both sides for n from 0 to infinity! This step is used to turn our recurrence into an equation describing F.
The last term is F(x). It's not so obvious what to do with our second last term, but we ultimately want to write it in terms of F(x). Here's what we do:
 = f_0 + f_1 x + f_2 x^2 + \ldots)
 - f_0}{x} = f_1 + f_2 x + \ldots)
But the RHS of this equation is just the second last term, so the second last term is
 - f_0}{x})
. In a similar fashion, you find that
 - f_0 - f_1 x}{x^2})
.
So we've turned out recurrence equation into
 - f_0 - f_1 x}{x^2} = \frac{F(x) - f_0}{x} + F(x))
. We know that
and
, so we can use this to solve for F(x), giving
 = \frac{x}{1-x-x^2})
. I expect you to perform this calculation.
Step 3. The idea of this stage is to expand our function as a series, to do that we'll be making use of the fact that
this is just the geometric series formula, so keep this in mind. We can use partial fractions to write
where r and r' are the roots of the denominator i.e. roots of
, and I'll suppose r is the positive root. I'll leave you to work out what r, r', A and B are. Once we've done that we can use our geometric series formula in reverse:
} = -\frac{A}{r} (1 + (x/r) + (x/r)^2 + \ldots) = \sum_{n=0}^\infty -\frac{A}{r^{n+1}} x^n)
So that
 = \frac{A}{x - r} + \frac{B}{x - r'} = \sum_{n=0}^\infty \left(-\frac{A}{r^{n+1}} - \frac{B}{r'^{n+1}}\right) x^n = \sum_{n=0}^\infty f_n x^n)
Equating coefficients gives us,
, which is Binet's formula.
Home
Help
Search
Login
