The Fibonacci Sequence

The Fibonacci sequence is a sequence of numbers starting withand uses the rule of adding the last two terms in the sequence to get the next term.

To get the third term add the first and second terms:1+1=2 and so on. We can define the sequence using the recurrence relation(1)

Proceeding like this we obtain the sequence

The Fibonacci sequence has several properties: The quotient of successive terms tend to a limit as we go further along the sequence:

(2)

The limit is in fact the 'Golden Ratio' that noticed by the ancient Greeks. and occurs in several natural phenomenon.

Proof:

(3)

In the recurrence relation (1) divide both sides byto giveNow letand substitute from (3)and obtainingThis can be rearranged into the quadratic equationthe solutions to which areand Obviously, looking at (2), we want the first of these values

In fact the limit above is more general. We can write down any two positive numbers and use them as the first two terms in a Fibonacci sequence, then

There is one more striking property revealed by a close examination of the sequence:

Proof is by induction:

Ifthenso the formula holds for

Suppose it holds forthen prove for

Now henceThe formula is proved.