Examples of Generating Functions - Worked Example B: Fibonacci Numbers

Worked Example B: Fibonacci Numbers

Consider the problem of finding a closed formula for the Fibonacci numbers Fn defined by F0 = 0, F1 = 1, and Fn = Fn−1 + Fn−2 for n ≥ 2. We form the ordinary generating function


f = sum_{n ge 0} F_n x^n

for this sequence. The generating function for the sequence (Fn−1) is xf and that of (Fn−2) is x2f. From the recurrence relation, we therefore see that the power series xf + x2f agrees with f except for the first two coefficients:


begin{array}{rcrcrcrcrcrcr}
f & = & F_0x^0 & + & F_1x^1 & + & F_2x^2 & + & cdots & + & F_ix^i & + &cdots\
xf & = & & & F_0x^1 & + & F_1x^2 & + & cdots & + &F_{i-1}x^i & + &cdots\
x^2f & = & & & & & F_0x^2 & + & cdots & + &F_{i-2}x^i & +&cdots\
(x+x^2)f & = & & & F_0x^1 & + & (F_0+F_1)x^2 & + & cdots & + & (F_{i-1}+F_{i-2})x^i & +&cdots\ & = & & & & & F_2x^2 & + & cdots & + & F_ix^i & +& cdots\
end{array}

Taking these into account, we find that


f = xf + x^2 f + x . ,!

(This is the crucial step; recurrence relations can almost always be translated into equations for the generating functions.) Solving this equation for f, we get


f = frac{x} {1 - x - x^2} .

The denominator can be factored using the golden ratio φ1 = (1 + √5)/2 and φ2 = (1 − √5)/2, and the technique of partial fraction decomposition yields


f = frac{1}{sqrt{5}} left (frac{1}{1-varphi_1 x} - frac{1} {1- varphi_2 x} right ) .

These two formal power series are known explicitly because they are geometric series; comparing coefficients, we find the explicit formula


F_n = frac{1} {sqrt{5}} (varphi_1^n - varphi_2^n).

Read more about this topic:  Examples Of Generating Functions

Famous quotes containing the word numbers:

    The only phenomenon with which writing has always been concomitant is the creation of cities and empires, that is the integration of large numbers of individuals into a political system, and their grading into castes or classes.... It seems to have favored the exploitation of human beings rather than their enlightenment.
    Claude Lévi-Strauss (b. 1908)