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
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:
Taking these into account, we find that
(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
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
These two formal power series are known explicitly because they are geometric series; comparing coefficients, we find the explicit formula
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)