Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Sum of Unit Fractions


Date: 07/17/2001 at 20:28:27
From: Candyce
Subject: Java programing class

Suppose that p/q is a fraction in lowest terms such that 
1/(n+1) < p/q < 1/n for some positive integer n. Show that 
(p/q) - (1/(n+1)) is a fraction which in its lowest terms has 
numerator less than p. Hence by induction, prove that every proper 
fraction p/q with p < q can be written as a finite sum of distinct 
reciprocals of positive integers. 

For example, 19/15 = 1/2 + 1/3 + 1/4 + 1/6 + 1/60. 

Use this technique to express 5/7 as a sum of reciprocals.

The example given here is correct, though it's not true that all 
fractions greater than 1 can be expressed finitely in this way 
(e.g. 2) - you've been asked to prove the statement only when the 
fraction is less than 1 (which is always true). If you want an 
example for this case, then 14/17 = 1/2 + 1/4 + 1/14 + 1/476. 

The problem is the PROFF part. I can understand that it works.


Date: 07/18/2001 at 10:53:15
From: Doctor Paul
Subject: Re: Java programing class

Here's how to do it for fractions less than one (assumed to be in 
lowest terms):

I'll show you how it works for 14/17 and you should be able to 
generalize 
it for any p/q.

Given 14/17, find the largest unit fraction less than 14/17. I think 
the easiest way to do this is to systematically increment the 
denominator by one until the fraction reduces to a unit fraction. The 
reduced unit fraction will be the largest unit fraction less than the 
given number. In the case of 14/17, we first consider: 14/18 = 7/9, 
which is not a unit fraction, so we next consider 14/19, 14/20 = 7/10, 
14/21 = 2/3, which is not a unit fraction, so we next consider 14/22, 
.... , 14/28 = 1/2.

So we know that 1/2 is a unit fraction and we know that it is less 
than 14/17.

Thus we can write:

  14/17 = 1/2 + a/b where a/b is to be determined.

subtract 1/2 from both sides to obtain:

  a/b = 14/17 - 1/2 = 11/34

Thus we have:

  14/17 = 1/2 + 11/34

If a/b had turned out to be a unit fraction, we would be done. But 
since it isn't a unit fraction, we do the process again. We now want 
to convert 11/34 into a sum of unit fractions:

Increase the denominator until you get a unit fraction:

  11/35, 11/36, ... , 11/44 = 1/4

  so 11/34 = 1/4 + c/d

Hence, 

  c/d = 11/34 - 1/4 = 5/68

So we have:

  14/17 = 1/2 + 1/4 + 5/68

If c/d had been a unit fraction, we would be done. But since c/d was 
equal to 5/68, we now need to repeat the process and convert 5/68 into 
a unit fraction.

increase denominators:

  5/68, ..., 5/70 = 1/14

so we have:

  5/68 = 1/14 + e/f

  e/f = 1/476

Since e/f is a unit fraction, we're done.

We can now write the final result:

  14/17 = 1/2 + 1/4 + 1/14 + 1/476, 

which is exactly the answer you gave above.

This method is attributed to the British mathematician J.J. Sylvester 
(1814-1897).

In general, the decomposition of a fraction into a sum of unit 
fractions is not unique. For example, 3/8 = 1/4 + 1/8 = 1/3 + 1/24.

Since your subject is "Java programming class" I'm guessing that you 
have to implement this algorithm in Java. Obviously, you're going to 
need to run some sort of 'for' or 'until' loop to get this thing to 
run properly. I've never programmed in Java, but I think it's a great 
assignment in any programming language! Good luck.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Calculators, Computers
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/