Recurrence Relation - Fibonacci Numbers

Fibonacci Numbers

The Fibonacci numbers are the archetype of a linear, homogeneous recurrence relation with constant coefficients (see below). They are defined using the linear recurrence relation

with seed values:

Explicitly, recurrence yields the equations:

etc.

We obtain the sequence of Fibonacci numbers which begins:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

It can be solved by methods described below yielding the closed-form expression which involve powers of the two roots of the characteristic polynomial t2 = t + 1; the generating function of the sequence is the rational function

Read more about this topic:  Recurrence Relation

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)