Subject: Re: Fibonacci sequence
Date: Sun, 23 Feb 1997 10:41:18 -0500
From: Alex Bogomolny

Dear Enuf:

Well, it's the famous Fibonacci sequence. One reason it's famous is that appears in so many often unexpected place and has so many different and curious properties that numerous chapters have been written about it. Named after Leonardo of Pisa son of Bonacci who described it in 1202 in his "Liber abaci".

The sequence is intimately related to the golden ratio t (I'll write t instead of ususal tau.) t = (1+5)/2.

If fn is the n-th Fibonacci number so that f0=0, f1=1, f2=1, f3=2, f4=3, ... and thus fn+1 = fn + fn-1, then

fn = (tn - (1-t)n)/5 which is due to Euler (1765).

The formula itself is remarkable. Writing it explicitly you may wonder how such an apparently irrational expression may lead to an integer number.

I'll list a few properties of the sequence:

1. The ratio fn+1/fn approaches the golden ratio as n grows.
2. fn+1*fn-1 - fn2 = (-1)n (Cassini's formula (1680))
3. fn and fn+1 are always relatively prime.
4. Any integer is a sum of distinct Fibonacci numbers.
5. fkn is a multiple of fn. Moreover,
6. gcd(fm, fn) = fgcd(m, n), (gcd - greatest common divisor)

You may be curious to look into the following books (check my Book store for details):

1. M.Gardner, Mathematical Circus
2. R.L.Graham et al, Concrete Mathematics
3. H.S.M.Coxeter, Introduction to Geometry

On Internet look into:

http://mathforum.org/dr.math/tocs/golden.high.html

or just run a search on the "Fibonacci Sequence" - results are sure to be overwhelming.

Best regards,
Alexander Bogomolny