Solving the Fibonacci recurrence with generating functions
posted by benzi
posted 1y 60d ago
The Fibonacci numbers are defined by F_0 = 1, F_1 = 1, and for n \geq 1,

F_{n+1} = F_{n-1} + F_n.

If we multiply both sides by x^n and sum from n=1 to infinity, we get

\sum_{n=1}^\infty F_{n+1}x^n \quad=\quad \sum_{n=1}^\infty F_{n-1}x^n \quad+\quad \sum_{n=1}^\infty F_n x^n.

If we let

u = \sum_{n=1}^\infty F_n x^n,
then u/x = F_1 + F_2x + F_3x^2 + \ldots, so the equation becomes

\frac{u}{x} - F_1 \quad=\quad (F_0x + ux) \quad+\quad u.

But F_1 = 1 and F_0 = 0, so this is

\frac{u}{x} - 1 = ux + u.

This can be solved for u:

u = \frac{x}{1 - x - x^2}.

When u is expanded as a power series about the origin, then, its coefficients are the Fibonacci numbers:

u \quad=\quad \frac{x}{1 - x - x^2} \quad=\quad x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + \cdots + F_nx^n + \cdots.
Reply to this post

Replies

Solving the Fibonacci recurrence with generating functions
posted by benzi
posted 1y 60d ago
Then this generating function can be broken into partial fractions: If

r_1 = \frac{-1 + \sqrt{5}}{2} \text{ and } r_2 = \frac{-1 - \sqrt{5}}{2}

are the roots of 1 - x - x^2 = 0, then

u = \frac{-x}{(x-r_1)(x-r_2)} = \frac{A}{x-r_1} + \frac{B}{x-r_2},

where
A = \frac{-r_1}{r_1 - r_2} \text{ and } B = \frac{r_2}{r_1 - r_2}.


r_1 - r_2 turns out to be \sqrt{5}, so

u \quad=\quad \frac{1}{\sqrt{5}}\left[ \frac{-r_1}{x-r_1} + \frac{r_2}{x-r_2} \right].


Each fraction can be expressed as a geometric series in x, i.e.,

u \quad=\quad \frac{1}{\sqrt{5}}\left[ \frac{1}{1 - x/r_1} - \frac{1}{1 - x/r_2} \right] \quad=\quad \frac{1}{\sqrt{5}}\left[ \left(1 + \frac{x}{r_1} + \left(\frac{x}{r_1}\right)^2 + \cdots\right) - \left(1 + \frac{x}{r_2} + \left(\frac{x}{r_2}\right)^2 + \cdots\right) \right].


In this series, the coefficient of x^n is \frac{1}{\sqrt{5}} \left[ \left(\frac{1}{r_2}\right)^n - \left(\frac{1}{r_2}\right)^n \right]. This is thus the nth Fibonacci number as above, so

F_n = \frac{1}{\sqrt{5}} \left[ \left(\frac{1}{r_2}\right)^n - \left(\frac{1}{r_2}\right)^n \right].
Use this to start your reply
Solving the Fibonacci recurrence with generating functions
posted by benzi
posted 1y 59d ago
In straight numbers, that's

F_n = \frac{1}{\sqrt{5}} \left[ \left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n \right].
Use this to start your reply
Submit Reply
Title: Your Name:
Wrap equations in [EQ]equation here[/EQ] tags, and inline equations in [IEQ][/IEQ] tags.