any rational number is a sum of unit fractions

Representation

Any rational number $\frac{a}{b}\in \mathbb{Q}$ between 0 and 1 can be represented as a sum of different unit fractions. This result was known to the Egyptians, whose way for representing rational numbers was as a sum of different unit fractions.

The following greedy algorithm can represent any as such a sum:

1. Let

   $$n=\lceil \frac{b}{a}\rceil$$

   be the smallest natural number for which $\frac{1}{n}\le \frac{a}{b}$. If $a=0$, terminate.

2. Output $\frac{1}{n}$ as the next term of the sum.

3. Continue from step 1, setting

   $$\frac{a^{\prime }}{b^{\prime }}=\frac{a}{b}-\frac{1}{n}.$$

Proof of correctness

Proof.

The algorithm can never output the same unit fraction twice. Indeed, any $n$ selected in step 1 is at least 2, so – so the same $n$ cannot be selected twice by the algorithm, as then $n-1$ could have been selected instead of $n$.

It remains to prove that the algorithm terminates. We do this by induction on $a$.

For $a=0$:

The algorithm terminates immediately.

For $a>0$:

The $n$ selected in step 1 satisfies

So

$$\frac{a}{b}-\frac{1}{n}=\frac{an-b}{bn},$$

and – by the induction hypothesis, the algorithm terminates for $\frac{a}{b}-\frac{1}{n}$.

∎

Problems

1. The greedy algorithm always works, but it tends to produce unnecessarily large denominators. For instance,

   $$\frac{47}{60}=\frac{1}{3}+\frac{1}{4}+\frac{1}{5},$$

   but the greedy algorithm selects $\frac{1}{2}$, leading to the representation

   $$\frac{47}{60}=\frac{1}{2}+\frac{1}{4}+\frac{1}{30}.$$

2. The representation is never unique. For instance, for any $n$ we have the representations

   $$\frac{1}{n}=\frac{1}{n+1}+\frac{1}{n\cdot (n+1)}$$

   So given any one representation of $\frac{a}{b}$ as a sum of different unit fractions we can take the largest denominator appearing $n$ and replace it with two (larger) denominators. Continuing the process indefinitely, we see infinitely many such representations, always.

Title	any rational number is a sum of unit fractions
Canonical name	AnyRationalNumberIsASumOfUnitFractions
Date of creation	2013-03-22 12:48:31
Last modified on	2013-03-22 12:48:31
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	7
Author	Mathprof (13753)
Entry type	Derivation
Classification	msc 11A67
Synonym	Egyptian algorithm