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:

    “I had but three chairs in my house; one for solitude, two for friendship; three for society. When visitors came in larger and unexpected numbers there was but the third chair for them all, but they generally economized the room by standing up.”
    —Henry David Thoreau (1817–1862)