Fibonacci Algorithm and Egyptian Fractions

Date: 04/25/99 at 19:06:37
From: liz
Subject: Egyptian fractions

I would like to know how to do 4 rounds in the Fibonacci algorithm. I 
have been able to get 3 rounds (521/1050 = 1/3 + 1/7 + 150 ) - could 
you please show me how to do 4 rounds with 2 examples? Also, I would 
like to know whether it is always possible to change any fraction into 
an Egyptian fraction using the decomposition method.

Thanks.
Liz

Date: 04/26/99 at 16:30:42
From: Doctor Rick
Subject: Re: Egyptian fractions

Hi, Liz, welcome to Ask Dr. Math!

The number of terms in an Egyptian fraction found by the Fibonacci 
algorithm depends only on what fraction you start with. There are 
fractions that lead to 4 or more terms using this method; one of these 
(the one with the smallest denominator) is 8/11. Try 16/17 too.

You can easily write an Egyptian fraction as long as you want. For 
instance, any unit fraction 1/n in your expansion can be replaced by 

  1/n = 1/(2n) + 1/(3n) + 1/(6n)

In your example,

  521/1050 = 1/3 + 1/7 + 1/50
           = (1/6 + 1/9 + 1/18) + 
             (1/14 + 1/21 + 1/42) + 
             (1/100 + 1/150 + 1/300)

There, we just multiplied the number of terms by 3, and you can 
multiply it by 3 again by replacing each of these terms, and so on 
forever. So finding long Egyptian fractions isn't a challenge; but 
finding the SHORTEST Egyptian fraction expansion for any given 
fraction is a challenge. The Fibonacci algorithm isn't guaranteed to 
find the shortest.

Take a look at this interesting Web site:

An Introduction to Egyptian Fractions (Ron Knott)
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fractions/egyptian.html   

It has lots of interesting information about Egyptian fractions, 
including the outline of a proof that the Fibonacci algorithm will 
produce an Egyptian fraction of finite length for any fraction. I 
don't know what you mean by the "decomposition method" so I can't say 
whether it will always work, if it's different from the Fibonacci 
method (and there are lots of methods).

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/