**Worked Example B: Fibonacci Numbers**

Consider the problem of finding a closed formula for the Fibonacci numbers *F*_{n} defined by *F*_{0} = 0, *F*_{1} = 1, and *F*_{n} = *F*_{n−1} + *F*_{n−2} for *n* ≥ 2. We form the ordinary generating function

for this sequence. The generating function for the sequence (*F*_{n−1}) is *xf* and that of (*F*_{n−2}) is *x*2*f*. From the recurrence relation, we therefore see that the power series *xf* + *x*2*f* 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)